An efficient algorithm for statistical multiple alignment on arbitrary phylogenetic trees.
We present an efficient algorithm for statistical multiple alignment based on the TKF91 model of Thorne, Kishino, and Felsenstein (1991) on an arbitrary k-leaved phylogenetic tree. The existing algorithms use a hidden Markov model approach, which requires at least O( radical 5(k)) states and leads t...
| Váldodahkkit: | , , , |
|---|---|
| Materiálatiipa: | Journal article |
| Giella: | English |
| Almmustuhtton: |
2003
|
| _version_ | 1826256860535062528 |
|---|---|
| author | Lunter, G Miklós, I Song, Y Hein, J |
| author_facet | Lunter, G Miklós, I Song, Y Hein, J |
| author_sort | Lunter, G |
| collection | OXFORD |
| description | We present an efficient algorithm for statistical multiple alignment based on the TKF91 model of Thorne, Kishino, and Felsenstein (1991) on an arbitrary k-leaved phylogenetic tree. The existing algorithms use a hidden Markov model approach, which requires at least O( radical 5(k)) states and leads to a time complexity of O(5(k)L(k)), where L is the geometric mean sequence length. Using a combinatorial technique reminiscent of inclusion/exclusion, we are able to sum away the states, thus improving the time complexity to O(2(k)L(k)) and considerably reducing memory requirements. This makes statistical multiple alignment under the TKF91 model a definite practical possibility in the case of a phylogenetic tree with a modest number of leaves. |
| first_indexed | 2024-03-06T18:08:58Z |
| format | Journal article |
| id | oxford-uuid:02598f96-b65e-4d67-a53b-c92648b083df |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T18:08:58Z |
| publishDate | 2003 |
| record_format | dspace |
| spelling | oxford-uuid:02598f96-b65e-4d67-a53b-c92648b083df2022-03-26T08:40:12ZAn efficient algorithm for statistical multiple alignment on arbitrary phylogenetic trees.Journal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:02598f96-b65e-4d67-a53b-c92648b083dfEnglishSymplectic Elements at Oxford2003Lunter, GMiklós, ISong, YHein, JWe present an efficient algorithm for statistical multiple alignment based on the TKF91 model of Thorne, Kishino, and Felsenstein (1991) on an arbitrary k-leaved phylogenetic tree. The existing algorithms use a hidden Markov model approach, which requires at least O( radical 5(k)) states and leads to a time complexity of O(5(k)L(k)), where L is the geometric mean sequence length. Using a combinatorial technique reminiscent of inclusion/exclusion, we are able to sum away the states, thus improving the time complexity to O(2(k)L(k)) and considerably reducing memory requirements. This makes statistical multiple alignment under the TKF91 model a definite practical possibility in the case of a phylogenetic tree with a modest number of leaves. |
| spellingShingle | Lunter, G Miklós, I Song, Y Hein, J An efficient algorithm for statistical multiple alignment on arbitrary phylogenetic trees. |
| title | An efficient algorithm for statistical multiple alignment on arbitrary phylogenetic trees. |
| title_full | An efficient algorithm for statistical multiple alignment on arbitrary phylogenetic trees. |
| title_fullStr | An efficient algorithm for statistical multiple alignment on arbitrary phylogenetic trees. |
| title_full_unstemmed | An efficient algorithm for statistical multiple alignment on arbitrary phylogenetic trees. |
| title_short | An efficient algorithm for statistical multiple alignment on arbitrary phylogenetic trees. |
| title_sort | efficient algorithm for statistical multiple alignment on arbitrary phylogenetic trees |
| work_keys_str_mv | AT lunterg anefficientalgorithmforstatisticalmultiplealignmentonarbitraryphylogenetictrees AT miklosi anefficientalgorithmforstatisticalmultiplealignmentonarbitraryphylogenetictrees AT songy anefficientalgorithmforstatisticalmultiplealignmentonarbitraryphylogenetictrees AT heinj anefficientalgorithmforstatisticalmultiplealignmentonarbitraryphylogenetictrees AT lunterg efficientalgorithmforstatisticalmultiplealignmentonarbitraryphylogenetictrees AT miklosi efficientalgorithmforstatisticalmultiplealignmentonarbitraryphylogenetictrees AT songy efficientalgorithmforstatisticalmultiplealignmentonarbitraryphylogenetictrees AT heinj efficientalgorithmforstatisticalmultiplealignmentonarbitraryphylogenetictrees |