Exact Asymptotic Results for a Model of Sequence Alignment

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 which reduces to the original model in the large c limit. 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. In particular, in the large c limit, this provides an exact expression for the asymptotic length distribution in the original LCS problem.

4 pages Revtex, 2 .eps figures included

References in corpus (2)

• Fluctuations of the one-dimensional polynuclear growth model with external sources
• An Anisotropic Ballistic Deposition Model with Links to the Ulam Problem and the Tracy-Widom Distribution

Cited by in corpus (32)

• Free-energy distribution of the directed polymer at high temperature
• Bethe anzats derivation of the Tracy-Widom distribution for one-dimensional directed polymers
• An exact solution for the KPZ equation with flat initial conditions
• Large Deviations of Extreme Eigenvalues of Random Matrices
• Extreme Value Statistics of Eigenvalues of Gaussian Random Matrices
• Extreme value statistics of correlated random variables: a pedagogical review
• Top eigenvalue of a random matrix: large deviations and third order phase transition
• Random Convex Hulls and Extreme Value Statistics
• On the top eigenvalue of heavy-tailed random matrices
• Non-interacting fermions at finite temperature in a $d$-dimensional trap: universal correlations
• Noninteracting fermions in a trap and random matrix theory
• Extreme value problems in Random Matrix Theory and other disordered systems
• Replica Bethe ansatz derivation of the Tracy-Widom distribution of the free energy fluctuations in one-dimensional directed polymers
• Multicritical edge statistics for the momenta of fermions in non-harmonic traps
• A simple derivation of the Tracy-Widom distribution of the maximal eigenvalue of a Gaussian unitary random matrix
• Random Matrix approach to collective behavior and bulk universality in protein dynamics
• One-dimensional stochastic growth and Gaussian ensembles of random matrices
• Finite N corrections to the limiting distribution of the smallest eigenvalue of Wishart complex matrices
• Attempted Bethe ansatz solution for one-dimensional directed polymers in random media
• Anomalous 1D fluctuations of a simple 2D random walk in a large deviation regime
• Large deviations of the top eigenvalue of large Cauchy random matrices
• A Central Limit Theorem for the Length of the Longest Common Subsequences in Random Words
• Probability distributions for directed polymers in random media with correlated noise
• Bethe Ansatz in the Bernoulli Matching Model of Random Sequence Alignment
• Brownian flights over a circle
• Exact solution of the Bernoulli matching model of sequence alignment
• New alphabet-dependent morphological transition in a random RNA alignment
• Mutually avoiding paths in random media and largests eigenvalues of random matrices
• Unzipping of two random heteropolymers: Ground state energy and finite size effects
• Tracy-Widom distributions for the Gaussian orthogonal and symplectic ensembles revisited: a skew-orthogonal polynomials approach
• Errata and Addenda to Mathematical Constants
• A novel Recurrence-Transience transition and Tracy-Widom growth in a cellular automaton with quenched noise