Evolutionary HMMs: a Bayesian approach to multiple alignment.
BACKGROUND
We review proposed syntheses of probabilistic sequence alignment, profiling and phylogeny. We develop a multiple alignment algorithm for Bayesian inference in the links model proposed by Thorne et al. (1991, J. Mol. Evol., 33, 114-124). The algorithm, described in detail in Section 3, samples from and/or maximizes the posterior distribution over multiple alignments for any number of DNA or protein sequences, conditioned on a phylogenetic tree. The individual sampling and maximization steps of the algorithm require no more computational resources than pairwise alignment.


METHODS
We present a software implementation (Handel) of our algorithm and report test results on (i) simulated data sets and (ii) the structurally informed protein alignments of BAliBASE (Thompson et al., 1999, Nucleic Acids Res., 27, 2682-2690).


RESULTS
We find that the mean sum-of-pairs score (a measure of residue-pair correspondence) for the BAliBASE alignments is only 13% lower for Handelthan for CLUSTALW(Thompson et al., 1994, Nucleic Acids Res., 22, 4673-4680), despite the relative simplicity of the links model (CLUSTALW uses affine gap scores and increased penalties for indels in hydrophobic regions). With reference to these benchmarks, we discuss potential improvements to the links model and implications for Bayesian multiple alignment and phylogenetic profiling.


BACKGROUND
The source code to Handelis freely distributed on the Internet at http://www.biowiki.org/Handel under the terms of the GNU Public License (GPL, 2000, http://www.fsf.org./copyleft/gpl.html).
Holmes
I
I
Group T10, Los Alamos National Laboratory, NM 87545, USA. ihh@fruitfly.org
Bruno
W J
WJ
D000465:Algorithms; D001499:Bayes Theorem; D003198:Computer Simulation; D030562:Databases, Protein; D019143:Evolution, Molecular; D006801:Humans; D008390:Markov Chains; D015233:Models, Statistical; D011506:Proteins / Q000737:chemistry; D016415:Sequence Alignment / Q000379:methods* / Q000706:statistics & numerical data*; D017422:Sequence Analysis, DNA / Q000706:statistics & numerical data; D012984:Software
D011506:Proteins