title: Exact asymptotic results for the Bernoulli matching 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. 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.
authors.affiliation: Laboratoire de Physique Theorique (UMR C5152 du CNRS), Université Paul Sabatier, 31062 Toulouse Cedex, France.
authors.forename: Satya N
authors.initials: SN
authors.lastname: Majumdar
authors.forename: Sergei
authors.initials: S
authors.lastname: Nechaev
mesh_terms: D016010:Binomial Distribution; D003198:Computer Simulation; D008956:Models, Chemical; D008957:Models, Genetic; D015233:Models, Statistical; D016415:Sequence Alignment / Q000379:methods*; D017421:Sequence Analysis / Q000379:methods*; D017385:Sequence Homology