Length of the Longest Common Subsequence between Overlapping Words

DOI10.1137/18M1176786zbMath1434.60037arXiv1803.03238MaRDI QIDQ5220470

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

DNA sequencingrandom wordscommon subsequences

Mathematics Subject Classification ID

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

Related Items (1)

Shuffle squares and reverse shuffle squares

Cites Work

• Unnamed Item
• Unnamed Item
• Some limit results for longest common subsequences
• The rate of convergence of the mean length of the longest common subsequence
• Standard deviation of the longest common subsequence
• Expected length of the longest common subsequence for large alphabets
• Improved bounds on the average length of longest common subsequences
• Longest common subsequences of two random sequences

This page was built for publication: Length of the Longest Common Subsequence between Overlapping Words