Phylogenetic automata, pruning, and multiple alignment
We present an extension of Felsenstein's algorithm to indel models defined on entire sequences, without the need to condition on one multiple alignment. The algorithm makes use of a generalization from probabilistic substitution matrices to weighted finite-state transducers. Our approach may eq...
| Main Authors: | , , , |
|---|---|
| Format: | Internet publication |
| Language: | English |
| Published: |
2011
|
| _version_ | 1811139782614450176 |
|---|---|
| author | Westesson, O Lunter, G Paten, B Holmes, I |
| author_facet | Westesson, O Lunter, G Paten, B Holmes, I |
| author_sort | Westesson, O |
| collection | OXFORD |
| description | We present an extension of Felsenstein's algorithm to indel models defined on entire sequences, without the need to condition on one multiple alignment. The algorithm makes use of a generalization from probabilistic substitution matrices to weighted finite-state transducers. Our approach may equivalently be viewed as a probabilistic formulation of progressive multiple sequence alignment, using partial-order graphs to represent ensemble profiles of ancestral sequences. We present a hierarchical stochastic approximation technique which makes this algorithm tractable for alignment analyses of reasonable size. |
| first_indexed | 2024-03-06T18:44:17Z |
| format | Internet publication |
| id | oxford-uuid:0df86d8d-2a79-4b5e-be0f-a97ad5b6ecf2 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-09-25T04:11:34Z |
| publishDate | 2011 |
| record_format | dspace |
| spelling | oxford-uuid:0df86d8d-2a79-4b5e-be0f-a97ad5b6ecf22024-06-26T15:30:36ZPhylogenetic automata, pruning, and multiple alignmentInternet publicationhttp://purl.org/coar/resource_type/c_7ad9uuid:0df86d8d-2a79-4b5e-be0f-a97ad5b6ecf2EnglishSymplectic Elements at Oxford2011Westesson, OLunter, GPaten, BHolmes, IWe present an extension of Felsenstein's algorithm to indel models defined on entire sequences, without the need to condition on one multiple alignment. The algorithm makes use of a generalization from probabilistic substitution matrices to weighted finite-state transducers. Our approach may equivalently be viewed as a probabilistic formulation of progressive multiple sequence alignment, using partial-order graphs to represent ensemble profiles of ancestral sequences. We present a hierarchical stochastic approximation technique which makes this algorithm tractable for alignment analyses of reasonable size. |
| spellingShingle | Westesson, O Lunter, G Paten, B Holmes, I Phylogenetic automata, pruning, and multiple alignment |
| title | Phylogenetic automata, pruning, and multiple alignment |
| title_full | Phylogenetic automata, pruning, and multiple alignment |
| title_fullStr | Phylogenetic automata, pruning, and multiple alignment |
| title_full_unstemmed | Phylogenetic automata, pruning, and multiple alignment |
| title_short | Phylogenetic automata, pruning, and multiple alignment |
| title_sort | phylogenetic automata pruning and multiple alignment |
| work_keys_str_mv | AT westessono phylogeneticautomatapruningandmultiplealignment AT lunterg phylogeneticautomatapruningandmultiplealignment AT patenb phylogeneticautomatapruningandmultiplealignment AT holmesi phylogeneticautomatapruningandmultiplealignment |