1204.1009 (S. Amsalu et al.)

Sparse long blocks and the variance of the LCS    [PDF]

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

Consider two random strings having the same length and generated by two mutually independent iid sequences taking values uniformly in a common finite alphabet. We study the order of the variance of the longest common subsequence (LCS) of these strings when long blocks, or other types of atypical substrings, are sparsely added into one of them. We show that the existence of the derivative of the mean LCS-curve at its maximum implies that this order is 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.

View original: http://arxiv.org/abs/1204.1009