Selected highlights of the Phylogenetic Alignment literature

Features of phylogenetic alignment

• PhylogeneticAlignment, aka StatisticalAlignment
  • aka StringTransducers, Evolutionary HMMs, Phylo-HMMs, Tree HMMs, Evolutionary SCFGs
• Explicit probabilistic representations for evolutionary models
• Stochastic grammars, sampled sequence trajectories on phylogenetic trees
• Combined Bayesian inference of phylogeny and alignment

Roots

• Likelihood phylogeny
  • Felsenstein J.  Evolutionary trees from DNA sequences: a maximum likelihood approach.  J Mol Evol. 1981;17(6):368-76.
• Maximum likelihood alignment
  • Bishop MJ, Thompson EA.  Maximum likelihood alignment of DNA sequences.  J Mol Biol. 1986 Jul 20;190(2):159-65.
• Minimum message length alignment & finite state machines
  • Allison L, Yee CN.  Minimum message length encoding and the comparison of macromolecules.  Bull Math Biol. 1990;52(3):431-53.
  • Allison L, Wallace CS, Yee CN.  Finite-state models in the alignment of macromolecules.  J Mol Evol. 1992 Jul;35(1):77-89.
• MCMC multiple alignment by Gibbs sampling
  • Lawrence CE, Altschul SF, Boguski MS, Liu JS, Neuwald AF, Wootton JC.  Detecting subtle sequence signals: a Gibbs sampling strategy for multiple alignment.  Science. 1993 Oct 8;262(5131):208-14.
• Paired-sequence hidden Markov models and stochastic grammars
  • The book BiologicalSequenceAnalysis by Durbin, Eddy, Krogh & Mitchison (1998)

Deriving phyloalignment algorithms from indel models

• Thorne JL, Kishino H, Felsenstein J.  An evolutionary model for maximum likelihood alignment of DNA sequences.  J Mol Evol. 1991 Aug;33(2):114-24. (PDF)
  • Arguably the central paper of the statistical phylo-alignment literature. Develops the most basic "TKF91 model" for pairwise alignment
• Hein J.  An algorithm for statistical alignment of sequences related by a binary tree.  Pac Symp Biocomput. 2001:179-90.
  • applies TKF91 to a tree
  • also M. Steel and J. Hein, Applying the Thorne–Kishino–Felsenstein model to sequence evolution on a star-shaped tree, Appl. Math. Lett. 14 (2001), p. 679.
• Holmes I, Bruno WJ.  Evolutionary HMMs: a Bayesian approach to multiple alignment.  Bioinformatics. 2001 Sep;17(9):803-20. (PDF)
  • develops MCMC for TKF91 using HMM theory
• Holmes I.  Using guide trees to construct multiple-sequence evolutionary HMMs.  Bioinformatics. 2003;19 Suppl 1:i147-57. (PDF) (errata)
  • constructs multi-sequence HMMs systematically by transducer composition
• Holmes I.  Phylocomposer and phylodirector: analysis and visualization of transducer indel models.  Bioinformatics. 2007 Dec 1;23(23):3263-4. Epub 2007 Sep 5. (pdf)
  • first implementation of a general-purpose phylogenetic transducer algorithm (more info here: PhyloComposer)
• Knudsen B, Miyamoto MM.  Sequence alignments and pair hidden Markov models using evolutionary history.  J Mol Biol. 2003 Oct 17;333(2):453-60.
  • Miklos I, Lunter GA, Holmes I.  A "Long Indel" model for evolutionary sequence alignment.  Mol Biol Evol. 2004 Mar;21(3):529-40. Epub 2003 Dec 23. (PDF)
  • Rivas E.  Evolutionary models for insertions and deletions in a probabilistic modeling framework.  BMC Bioinformatics. 2005 Mar 21;6:63.
  • time-dependent affine gap penalties for transducers
• Lunter G, Miklos I, Drummond A, Jensen JL, Hein J.  Bayesian coestimation of phylogeny and sequence alignment.  BMC Bioinformatics. 2005 Apr 1;6:83.
  • Redelings BD, Suchard MA.  Joint Bayesian estimation of alignment and phylogeny.  Syst Biol. 2005 Jun;54(3):401-18.
  • Metzler D, Fleissner R, Wakolbinger A, von Haeseler A.  Assessing variability by joint sampling of alignments and mutation rates.  J Mol Evol. 2001 Dec;53(6):660-9.
  • MCMC samplers

Beyond point substitution models

• Robinson DM, Jones DT, Kishino H, Goldman N, Thorne JL.  Protein evolution with dependence among codons due to tertiary structure.  Mol Biol Evol. 2003 Oct;20(10):1692-704. Epub 2003 Jul 28.
• Lunter G, Hein J.  A nucleotide substitution model with nearest-neighbour interactions.  Bioinformatics. 2004 Aug 4;20 Suppl 1:i216-23.
• Siepel A, Haussler D.  Phylogenetic estimation of context-dependent substitution rates by maximum likelihood.  Mol Biol Evol. 2004 Mar;21(3):468-88. Epub 2003 Dec 5.

RNA models

• Knudsen B, Hein J.  Pfold: RNA secondary structure prediction using stochastic context-free grammars.  Nucleic Acids Res. 2003 Jul 1;31(13):3423-8.
• Holmes I.  A probabilistic model for the evolution of RNA structure.  BMC Bioinformatics. 2004 Oct 26;5:166. (PDF)
  • Nested TKF91 models for stems and loops; tree transducers
• Matsui H, Sato K, Sakakibara Y.  Pair stochastic tree adjoining grammars for aligning and predicting pseudoknot RNA structures.  Bioinformatics. 2005 Jun 1;21(11):2611-7. Epub 2005 Mar 22.

Protein models

• Goldman N, Thorne JL, Jones DT.  Using evolutionary trees in protein secondary structure prediction and other comparative sequence analyses.  J Mol Biol. 1996 Oct 25;263(2):196-208.

Other papers following from TKF91

• Thorne JL, Kishino H, Felsenstein J.  Inching toward reality: an improved likelihood model of sequence evolution.  J Mol Evol. 1992 Jan;34(1):3-16.
  • the "TKF92 model"
• Thorne JL, Churchill GA.  Estimation and reliability of molecular sequence alignments.  Biometrics. 1995 Mar;51(1):100-13.
• Miklos I.  An improved algorithm for statistical alignment of sequences related by a star tree.  Bull Math Biol. 2002 Jul;64(4):771-9.
• Hein J, Wiuf C, Knudsen B, Moller MB, Wibling G.  Statistical alignment: computational properties, homology testing and goodness-of-fit.  J Mol Biol. 2000 Sep 8;302(1):265-79.
• Metzler D.  Statistical alignment based on fragment insertion and deletion models.  Bioinformatics. 2003 Mar 1;19(4):490-9.
• Holmes I.  Using evolutionary Expectation Maximization to estimate indel rates.  Bioinformatics. 2005 May 15;21(10):2294-300. Epub 2005 Feb 24. (PDF)
• Lunter GA, Miklos I, Song YS, Hein J.  An efficient algorithm for statistical multiple alignment on arbitrary phylogenetic trees.  J Comput Biol. 2003;10(6):869-89.
• Jojic V, Jojic N, Meek C, Geiger D, Siepel A, Haussler D, Heckerman D.  Efficient approximations for learning phylogenetic HMM models from data.  Bioinformatics. 2004 Aug 4;20 Suppl 1:i161-8.
• Siepel A, Haussler D.  Combining phylogenetic and hidden Markov models in biosequence analysis.  J Comput Biol. 2004;11(2-3):413-28.
• Metzler D.  Statistical alignment based on fragment insertion and deletion models.  Bioinformatics. 2003 Mar 1;19(4):490-9.

Reading the indel-rate signal

• Lunter G, Ponting CP, Hein J.  Genome-wide identification of human functional DNA using a neutral indel model.  PLoS Comput Biol. 2006 Jan;2(1):e5. Epub 2006 Jan 13.

Reconstruction of indel history

In light of the interest in ancestral genome reconstruction, several authors have approached the problem of indel modeling from this slightly different direction. Typically these approaches require the input alignment to be specified and this leads the authors to a slightly different formalism, although the methods can still be reformulated within the framework of string transducers.

• Blanchette et al
  • Diallo AB, Makarenkov V, Blanchette M.  Exact and heuristic algorithms for the Indel Maximum Likelihood Problem.  J Comput Biol. 2007 May;14(4):446-61.
  • Chindelevitch L, Li Z, Blais E, Blanchette M.  On the inference of parsimonious indel evolutionary scenarios.  J Bioinform Comput Biol. 2006 Jun;4(3):721-44.
• Sinha et al
  • Kim J, Sinha S.  Indelign: a probabilistic framework for annotation of insertions and deletions in a multiple alignment.  Bioinformatics. 2007 Feb 1;23(3):289-97. Epub 2006 Nov 15.
• Ortheus: Paten, Birney et al
  • Paten B, Herrero J, Fitzgerald S, Beal K, Flicek P, Holmes I, Birney E.  Genome-wide nucleotide-level mammalian ancestor reconstruction.  Genome Res. 2008 Nov;18(11):1829-43. doi: 10.1101/gr.076521.108. Epub 2008 Oct 10.
• MichaelJordan and Alexandre Bouchard-Côté
  • Alexandre Bouchard-Côté, Michael I. Jordan and Dan Klein. (2009) Efficient Inference in Phylogenetic InDel Trees. Advances in Neural Information Processing Systems 21 (NIPS). Vancouver, Canada. (paper)
  • Poster & slides here: http://www.stat.ubc.ca/~bouchard/