title: Scaling statistical multiple sequence alignment to large datasets.
abstract: Multiple sequence alignment is an important task in bioinformatics, and alignments of large datasets containing hundreds or thousands of sequences are increasingly of interest. While many alignment methods exist, the most accurate alignments are likely to be based on stochastic models where sequences evolve down a tree with substitutions, insertions, and deletions. While some methods have been developed to estimate alignments under these stochastic models, only the Bayesian method BAli-Phy has been able to run on even moderately large datasets, containing 100 or so sequences. A technique to extend BAli-Phy to enable alignments of thousands of sequences could potentially improve alignment and phylogenetic tree accuracy on large-scale data beyond the best-known methods today.
  
  
  
  We use simulated data with up to 10,000 sequences representing a variety of model conditions, including some that are significantly divergent from the statistical models used in BAli-Phy and elsewhere. We give a method for incorporating BAli-Phy into PASTA and UPP, two strategies for enabling alignment methods to scale to large datasets, and give alignment and tree accuracy results measured against the ground truth from simulations. Comparable results are also given for other methods capable of aligning this many sequences.
  
  
  
  Extensions of BAli-Phy using PASTA and UPP produce significantly more accurate alignments and phylogenetic trees than the current leading methods.
authors.affiliation: Department of Statistics, University of Illinois at Urbana-Champaign, 725 S. Wright St, Champaign, 61820, IL, USA.
authors.forename: Michael
authors.initials: M
authors.lastname: Nute
authors.affiliation: Department of Computer Science, University of Illinois at Urbana-Champaign, 201 North Goodwin Ave, Urbana, 61801, IL, USA. warnow@illinois.edu.|Department of Bioengineering, University of Illinois at Urbana-Champaign, 1270 Digital Computing Laboratory, MC-278, Urbana, 61801, IL, USA. warnow@illinois.edu.|National Center for Supercomputing Applications, University of Illinois at Urbana-Champaign, 1205 W. Clark St., MC-257, Urbana, 61801, IL, USA. warnow@illinois.edu.|Carl R. Woese Institute for Genomic Biology, University of Illinois at Urbana-Champaign, 1206 W. Gregory Dr., MC-195, Urbana, 61801, IL, USA. warnow@illinois.edu.
authors.forename: Tandy
authors.initials: T
authors.lastname: Warnow
mesh_terms: D000465:Algorithms; D001499:Bayes Theorem; D019295:Computational Biology / Q000379:methods*; D030541:Databases, Genetic; D016415:Sequence Alignment
keywords: Boosting; MCMC; Multiple sequence alignment