Distribution of Aligned Letter Pairs in Optimal Alignments of Random Sequences
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....
| Main Authors: | , |
|---|---|
| Format: | Report |
| Published: |
Annals of Probability
2012
|
| _version_ | 1826274402934718464 |
|---|---|
| author | Hauser, R Matzinger, H |
| author_facet | Hauser, R Matzinger, H |
| author_sort | Hauser, R |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-06T22:42:54Z |
| format | Report |
| id | oxford-uuid:5c32bc2b-dd48-4041-bcf5-9eedeaee7b37 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T22:42:54Z |
| publishDate | 2012 |
| publisher | Annals of Probability |
| record_format | dspace |
| spelling | oxford-uuid:5c32bc2b-dd48-4041-bcf5-9eedeaee7b372022-03-26T17:26:37ZDistribution of Aligned Letter Pairs in Optimal Alignments of Random SequencesReporthttp://purl.org/coar/resource_type/c_93fcuuid:5c32bc2b-dd48-4041-bcf5-9eedeaee7b37Mathematical Institute - ePrintsAnnals of Probability2012Hauser, RMatzinger, HConsidering 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. |
| spellingShingle | Hauser, R Matzinger, H Distribution of Aligned Letter Pairs in Optimal Alignments of Random Sequences |
| title | Distribution of Aligned Letter Pairs in Optimal Alignments of Random Sequences |
| title_full | Distribution of Aligned Letter Pairs in Optimal Alignments of Random Sequences |
| title_fullStr | Distribution of Aligned Letter Pairs in Optimal Alignments of Random Sequences |
| title_full_unstemmed | Distribution of Aligned Letter Pairs in Optimal Alignments of Random Sequences |
| title_short | Distribution of Aligned Letter Pairs in Optimal Alignments of Random Sequences |
| title_sort | distribution of aligned letter pairs in optimal alignments of random sequences |
| work_keys_str_mv | AT hauserr distributionofalignedletterpairsinoptimalalignmentsofrandomsequences AT matzingerh distributionofalignedletterpairsinoptimalalignmentsofrandomsequences |