Distribution of Aligned Letter Pairs in Optimal Alignments of Random Sequences

arXiv1211.5491MaRDI QIDQ6237410FDOQ6237410

Authors: Raphael A. Hauser, Heinrich Matzinger 

Publication date: 23 November 2012

Abstract: Considering the optimal alignment of two i.i.d. random sequences of length $n$, we show that when the scoring function is chosen randomly, almost surely the empirical distribution of aligned letter pairs in all optimal alignments converges to a unique limiting distribution as $n$ tends to infinity. This result is interesting because it helps understanding the microscopic path structure of a special type of last passage percolation problem with correlated weights, an area of long-standing open problems. Characterizing the microscopic path structure yields furthermore a robust alternative to optimal alignment scores for testing the relatedness of genetic sequences.

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Large deviations (60F10) Asymptotic distribution theory in statistics (62E20) Geometric probability and stochastic geometry (60D05) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Combinatorial optimization (90C27) Combinatorial probability (60C05) Inequalities and extremum problems involving convexity in convex geometry (52A40)

This page was built for publication: Distribution of Aligned Letter Pairs in Optimal Alignments of Random Sequences

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