Sparse long blocks and the variance of the longest common subsequences in random words

S. Amsalu, C. Houdré, H. Matzinger

Published 2012-04-04, updated 2016-09-23Version 2

Consider two independent random strings having same length and taking values uniformly in a common finite alphabet. We study the order of the variance of the length of the longest common subsequences (LCS) of these strings when long blocks, or other types of atypical substrings, are sparsely added into one of them. Under weak conditions on the derivative of the mean LCS-curve, the order of the variance of the LCS is shown to be linear in the length of the strings. We also argue that our proofs carry over to many models used by computational biologists to simulate DNA-sequences. This is the first result where the open question of the order of the fluctuation of the LCS of random strings is solved for a realistic model. Until now, this type of result had only been established for low entropy cases.