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

arXiv1204.1009MaRDI QIDQ6232093FDOQ6232093

Saba Amsalu, Christian Houdré, Heinrich Matzinger

Publication date: 4 April 2012

Abstract: 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.

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Combinatorial probability (60C05) Asymptotic enumeration (05A16)

This page was built for publication: Sparse long blocks and the variance of the longest common subsequences in random words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6232093)