2012/11/23 by Raphael Hauser, Hauser, Raphael, Heinrich Matzinger +1
Computer Science · Mathematics · #60C05 #60D05 #60F10 #60K35 (Primary) 52A40 #62E20 #65K10 #90C27 (Secondary) #Algorithms and Data Compression #Bayesian Methods and Mixture Models #FOS: Mathematics #Probability (math.PR) #Stochastic processes and statistical mechanics #math.PR #msc:52A40 #msc:60C05 #msc:60D05 #msc:60F10 #msc:60K35 #msc:62E20 #msc:65K10 #msc:90C27
paper · pdf · doi:10.48550/arxiv.1211.5491
arxiv created 2012/11/23 · openalex publication_date 2012/11/23 · arxiv updated 2012/11/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.