title: Evolutionary HMMs: a Bayesian approach to multiple alignment.
abstract: 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).
authors.affiliation: Group T10, Los Alamos National Laboratory, NM 87545, USA. ihh@fruitfly.org
authors.forename: I
authors.initials: I
authors.lastname: Holmes
authors.forename: W J
authors.initials: WJ
authors.lastname: Bruno
mesh_terms: 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
chemical_list: D011506:Proteins