Simulations, Computations, and Statistics for Longest Common Subsequences
Qingqing Liu, Christian Houdré · arXiv (Cornell University) · 2017
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.