Using guide trees to construct multiple-sequence evolutionary HMMs.
BACKGROUND
Score-based progressive alignment algorithms do dynamic programming on successive branches of a guide tree. The analogous probabilistic construct is an Evolutionary HMM. This is a multiple-sequence hidden Markov model (HMM) made by combining transducers (conditionally normalised Pair HMMs) on the branches of a phylogenetic tree.


METHODS
We present general algorithms for constructing an Evolutionary HMM from any Pair HMM and for doing dynamic programming to any Multiple-sequence HMM.


RESULTS
Our prototype implementation, Handel, is based on the Thorne-Kishino-Felsenstein evolutionary model and is benchmarked using structural reference alignments.
Holmes
I
I
Department of Statistics, University of Oxford. 1 South Parks Road, Oxford OX1 3TG, UK.
D000465:Algorithms; D016000:Cluster Analysis; D019143:Evolution, Molecular; D020869:Gene Expression Profiling / Q000379:methods*; D005786:Gene Expression Regulation / Q000235:genetics; D008390:Markov Chains; D008957:Models, Genetic; D015233:Models, Statistical; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*; D020539:Sequence Analysis, Protein / Q000379:methods*; D017385:Sequence Homology; D012984:Software