Exact asymptotic results for the Bernoulli matching model of sequence alignment
Authors:
- 2 August 2005
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 72 (2) , 020901
Abstract
Finding analytically the statistics of the longest common subsequence (LCS) of a pair of random sequences drawn from c alphabets is a challenging problem in computational evolutionary biology. We present exact asymptotic results for the distribution of the LCS in a simpler, yet nontrivial, variant of the original model called the Bernoulli matching (BM) model. We show that in the BM model, for all c , the distribution of the asymptotic length of the LCS, suitably scaled, is identical to the Tracy-Widom distribution of the largest eigenvalue of a random matrix whose entries are drawn from a Gaussian unitary ensemble.Keywords
All Related Versions
This publication has 28 references indexed in Scilit:
- Anisotropic ballistic deposition model with links to the Ulam problem and the Tracy-Widom distributionPhysical Review E, 2004
- Similarity Detection and LocalizationPhysical Review Letters, 1996
- Alignment of molecular sequences seen as random path analysisJournal of Theoretical Biology, 1995
- The Rate of Convergence of the Mean Length of the Longest Common SubsequenceThe Annals of Applied Probability, 1994
- Level-spacing distributions and the Airy kernelCommunications in Mathematical Physics, 1994
- Basic local alignment search toolJournal of Molecular Biology, 1990
- The longest common subsequence problem revisitedAlgorithmica, 1987
- Identification of common molecular subsequencesJournal of Molecular Biology, 1981
- Longest common subsequences of two random sequencesJournal of Applied Probability, 1975
- A general method applicable to the search for similarities in the amino acid sequence of two proteinsJournal of Molecular Biology, 1970