An efficient algorithm for statistical multiple alignment on arbitrary phylogenetic trees. Export

@article{citeulike:3643952, abstract = {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.}, author = {Lunter, G. A. and Mikl\'{o}s, I. and Song, Y. S. and Hein, J.}, citeulike-article-id = {3643952}, citeulike-linkout-0 = {http://dx.doi.org/10.1089/106652703322756122}, citeulike-linkout-1 = {http://view.ncbi.nlm.nih.gov/pubmed/14980015}, citeulike-linkout-2 = {http://www.hubmed.org/display.cgi?uids=14980015}, doi = {10.1089/106652703322756122}, issn = {1066-5277}, journal = {Journal of computational biology : a journal of computational molecular cell biology}, keywords = {algorithm, multiple, phylogenetic, statistical-alignment, trees}, number = {6}, pages = {869--889}, posted-at = {2008-11-21 10:34:10}, priority = {2}, title = {An efficient algorithm for statistical multiple alignment on arbitrary phylogenetic trees.}, url = {http://dx.doi.org/10.1089/106652703322756122}, volume = {10}, year = {2003} }

TY - JOUR ID - citeulike:3643952 L3 - citeulike-article-id:3643952 N2 - 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. IS - 6 JF - Journal of computational biology : a journal of computational molecular cell biology SN - 1066-5277 EP - 889 TI - An efficient algorithm for statistical multiple alignment on arbitrary phylogenetic trees. VL - 10 SP - 869 KW - algorithm KW - multiple KW - phylogenetic KW - statistical-alignment KW - trees AU - Lunter, GA AU - Miklós, I AU - Song, YS AU - Hein, J PY - 2003/// UR - http://dx.doi.org/10.1089/106652703322756122 ER -