Length of the longest common subsequence between overlapping words

DOI10.1137/18M1176786MaRDI QIDQ5220470zbMATH OpenFDO

Authors Boris Bukh, Raymond Hogenson

Publication date 26 March 2020

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.03238

zbMATH Keywords

common subsequencesDNA sequencingrandom words

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial probability (60C05) Combinatorics on words (68R15) Statistical mechanics of solids (82D20)

Abstract: Given two random finite sequences from $[k{]}^n$ such that a prefix of the first sequence is a suffix of the second, we examine the length of their longest common subsequence. If $ell$ is the length of the overlap, we prove that the expected length of an LCS is approximately $max(ell,mathbbE[L_n])$, where $L_n$ is the length of an LCS between two independent random sequences. We also obtain tail bounds on this quantity.

Recommendations

• LATIN 2004: Theoretical Informatics
• Expected length of the longest common subsequence for large alphabets
• On the order of the central moments of the length of the longest common subsequences in random words
• Longest common subsequences
• Common Subsequences and Supersequences and their Expected Length

Cites work

• Expected length of the longest common subsequence for large alphabets
• Fluctuations of the longest common subsequence in the asymmetric case of 2- and 3-letter alphabets
• Improved bounds on the average length of longest common subsequences
• Longest common subsequences of two random sequences
• Some limit results for longest common subsequences
• Standard deviation of the longest common subsequence
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The rate of convergence of the mean length of the longest common subsequence

Cited in

(2)

• Longest Common Extensions in Partial Words
• Shuffle squares and reverse shuffle squares

This page was built for publication: Length of the longest common subsequence between overlapping words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5220470)