Simulations, Computations, and Statistics for Longest Common Subsequences

2017/05/18 by Liu, Qingqing, Houdré, Christian
#05A05 #60C05 #62F03 #65C05 #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1705.06826

Abstract

The length of the longest common subsequences (LCSs) is often used as a similarity measurement to compare two (or more) random words. Below we study its statistical behavior in mean and variance using a Monte-Carlo approach from which we then develop a hypothesis testing method for sequences similarity. Finally, theoretical upper bounds are obtained for the Chvátal-Sankoff constant of multiple sequences.

Related

• Systematic assessment of the expected length, variance and distribution of Longest Common Subsequences
• Repetition-free longest common subsequence of random sequences
• Length of the longest common subsequence between overlapping words
• Expected Length of the Longest Common Subsequence of Multiple Strings
• Longest common subsequences in binary sequences