arXiv:1705.06826 Abstract | arXiv Analytics

arXiv:1705.06826 [math.PR]Abstract References Reviews Resources

Simulations, Computations, and Statistics for Longest Common Subsequences

Published 2017-05-18Version 1

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\'atal-Sankoff constant of multiple sequences.

Comments: 12 pages, 10 figures

Categories: math.PR

Subjects: 65C05, 62F03, 60C05, 05A05

Keywords: longest common subsequences, simulations, statistics, computations, chvatal-sankoff constant

Related articles: Most relevant | Search more

arXiv:1703.07691 [math.PR] (Published 2017-03-22)

A Note on the Expected Length of the Longest Common Subsequences of two i.i.d. Random Permutations

Christian Houdré, Chen Xu

arXiv:1812.09552 [math.PR] (Published 2018-12-22)

On the Variance of the Length of the Longest Common Subsequences in Random Words With an Omitted Letter

Christian Houdré, Qingqing Liu

arXiv:1803.04052 [math.PR] (Published 2018-03-11)