Aarhus University Seal

Recursions for Statistical Multiple Alignment

by Jotun Hein, Jens Ledet Jensen and Christian N.S. Pedersen
Research Reports Number 425 (January 2002)
Algorithms are presented that allows 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 recursions are based on a Markov chain generating sequences and their alignment at nodes in a tree. Dependent 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 are $O(prod_{i=1}^d L_i)$, where $L_i$ is the length of the $i$´th observed sequence and $d$ is the number of sequences - leaves at the binary tree. An alternative recursion is also formulated that only uses a Markov chain involving the internal nodes of a tree.
Format available: PDF (318 KB)