© 2005 Society of Systematic Biologists
Joint Bayesian Estimation of Alignment and Phylogeny
Department of Biomathematics, David Geffen School of Medicine at UCLA Los Angeles, California, 90095–1766, USA E-mail: msuchard{at}ucla.edu (M.A.S.)
Edited by Paul Lewis: Associate Editor
 |
Abstract |
|---|
We describe a novel model and algorithm for simultaneously estimating multiple molecular sequence alignments and the phylogenetic trees that relate the sequences. Unlike current techniques that base phylogeny estimates on a single estimate of the alignment, we take alignment uncertainty into account by considering all possible alignments. Furthermore, because the alignment and phylogeny are constructed simultaneously, a guide tree is not needed. This sidesteps the problem in which alignments created by progressive alignment are biased toward the guide tree used to generate them. Joint estimation also allows us to model rate variation between sites when estimating the alignment and to use the evidence in shared insertion/deletions (indels) to group sister taxa in the phylogeny. Our indel model makes use of affine gap penalties and considers indels of multiple letters. We make the simplifying assumption that the indel process is identical on all branches. As a result, the probability of a gap is independent of branch length. We use a Markov chain Monte Carlo (MCMC) method to sample from the posterior of the joint model, estimating the most probable alignment and tree and their support simultaneously. We describe a new MCMC transition kernel that improves our algorithm's mixing efficiency, allowing the MCMC chains to converge even when started from arbitrary alignments. Our software implementation can estimate alignment uncertainty and we describe a method for summarizing this uncertainty in a single plot.
Keywords: Alignment bias; Bayesian phylogenetics; indel models; MCMC; statistical alignment; Tree of Life
Received April 13, 2004; Revised July 7, 2004; Accepted November 5, 2004
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  A. Kitchen, C. Ehret, S. Assefa, and C. J. Mulligan Bayesian phylogenetic analysis of Semitic languages identifies an Early Bronze Age origin of Semitic in the Near East Proc R Soc B, August 7, 2009; 276(1668): 2703 - 2710. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 K. Liu, S. Raghavan, S. Nelesen, C. R. Linder, and T. Warnow Rapid and Accurate Large-Scale Coestimation of Sequence Alignments and Phylogenetic Trees Science, June 19, 2009; 324(5934): 1561 - 1564. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 B. Misof and K. Misof A Monte Carlo Approach Successfully Identifies Randomness in Multiple Sequence Alignments: A More Objective Means of Data Exclusion Syst Biol, May 20, 2009; (2009) syp006v1. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 R. A. Cartwright Problems and Solutions for Estimating Indel Rates and Length Distributions Mol. Biol. Evol., February 1, 2009; 26(2): 473 - 480. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 S. C. Choi, B. D Redelings, and J. L Thorne Basing population genetic inferences and models of molecular evolution upon desired stationary distributions of DNA or protein sequences Phil Trans R Soc B, December 27, 2008; 363(1512): 3931 - 3939. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
K. Somogyi, B. Sipos, Z. Penzes, E. Kurucz, J. Zsamboki, D. Hultmark, and I. Ando Evolution of Genes and Repeats in the Nimrod Superfamily Mol. Biol. Evol., November 1, 2008; 25(11): 2337 - 2347. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 A. Novak, I. Miklos, R. Lyngso, and J. Hein StatAlign: an extendable software package for joint Bayesian estimation of alignments and evolutionary trees Bioinformatics, October 15, 2008; 24(20): 2403 - 2404. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
A. D. Fernandes and W. R. Atchley Site-specific evolutionary rates in proteins are better modeled as non-independent and strictly relative Bioinformatics, October 1, 2008; 24(19): 2177 - 2183. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
K. M. Wong, M. A. Suchard, and J. P. Huelsenbeck Alignment Uncertainty and Genomic Analysis Science, January 25, 2008; 319(5862): 473 - 476. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
E. Benavides, R. Baum, D. McClellan, and J. W. Sites Molecular Phylogenetics of the Lizard Genus Microlophus (Squamata:Tropiduridae): Aligning and Retrieving Indel Signal from Nuclear Introns Syst Biol, October 1, 2007; 56(5): 776 - 797. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 P. R. Teske, N. P. Barker, and C. D. McQuaid Lack of genetic differentiation among four sympatric southeast African intertidal limpets (Siphonariidae): phenotypic plasticity in a single species? J. Mollus. Stud., August 1, 2007; 73(3): 223 - 228. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
G. Talavera and J. Castresana Improvement of Phylogenies after Removing Divergent and Ambiguously Aligned Blocks from Protein Sequence Alignments Syst Biol, August 1, 2007; 56(4): 564 - 577. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
T. H. Ogden and M. S. Rosenberg Alignment and Topological Accuracy of the Direct Optimization approach via POY and Traditional Phylogenetics via ClustalW + PAUP Syst Biol, April 1, 2007; 56(2): 182 - 193. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 S. Kumar and A. Filipski Multiple sequence alignment: In pursuit of homologous DNA positions Genome Res., February 1, 2007; 17(2): 127 - 135. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
K. M. Kjer, J. J. Gillespie, and K. A. Ober Opinions on Multiple Sequence Alignment, and an Empirical Comparison of Repeatability and Accuracy between POY and Structural Alignment Syst Biol, February 1, 2007; 56(1): 133 - 146. [Full Text] [PDF]
|
|
|
|
|
|
M. A. Suchard and B. D. Redelings BAli-Phy: simultaneous Bayesian inference of alignment and phylogeny Bioinformatics, August 15, 2006; 22(16): 2047 - 2048. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
T. H. Ogden and M. S. Rosenberg Multiple Sequence Alignment Accuracy and Phylogenetic Inference Syst Biol, April 1, 2006; 55(2): 314 - 328. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
M. T. Holder, P. O. Lewis, D. L. Swofford, and B. Larget Hastings Ratio of the LOCAL Proposal Used in Bayesian Phylogenetics Syst Biol, December 1, 2005; 54(6): 961 - 965. [Full Text] [PDF]
|
|