Using guide trees to construct multiple-sequence evolutionary HMMs

Open Access
Publisher Website
Google Scholar
Abstract
Motivation: 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. Availability: Handel can be downloaded under GPL from www.biowiki.org/Handel

This publication has 0 references indexed in Scilit: