期刊名称：Proceedings of the National Academy of Sciences
印刷版ISSN：0027-8424
电子版ISSN：1091-6490
出版年度：2003
卷号：100
期号：25
页码：14960-14965
DOI：10.1073/pnas.2036252100
语种：English
出版社：The National Academy of Sciences of the United States of America
摘要：Algorithms are presented that allow the calculation of the probability of a set of sequences related by a binary tree that have evolved according to the Thorne-Kishino-Felsenstein model for a fixed set of parameters. The algorithms are based on a Markov chain generating sequences and their alignment at nodes in a tree. Depending on whether the complete realization of this Markov chain is decomposed into the first transition and the rest of the realization or the last transition and the first part of the realization, two kinds of recursions are obtained that are computationally similar but probabilistically different. The running time of the algorithms is [IMG]f1.gif" ALT="Formula" BORDER="0">, where Li is the length of the ith observed sequences and d is the number of sequences. An alternative recursion is also formulated that uses only a Markov chain involving the inner nodes of a tree.
关键词：backward recursion ; emission probability ; forward recursion ; hidden Markov chain ; states
