Simulations, Computations, and Statistics for Longest Common Subsequences
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.
arXiv comment12 pages, 10 figures
References in corpus (4)
- A Central Limit Theorem for the Length of the Longest Common Subsequences in Random Words
- High precision simulations of the longest common subsequence problem
- Sparse long blocks and the variance of the longest common subsequences in random words
- Systematic assessment of the expected length, variance and distribution of Longest Common Subsequences