Large-Scale Simultaneous Multiple Alignment and Phylogeny Estimation

This project is funded by NSF DEB 0733029 (ATOL), and is a collaboration between the University of Texas, the University of Georgia, The University of Nebraska, and the University of Kansas.

Main goals

New methods for simultaneous estimation of alignments and trees.
New simulator tools for evolution which produce more realistic data (including rearrangements, duplications, and indels)
Educational outreach

Workshop and Symposium Announcement

We will hold a Workshop and Symposium on new methods for alignment and tree estimation, to be held at the Smithsonian Institution in Washington, DC, on May 20-22, 2012. Travel support will be provided, but participation is limited to 40 attendees. Registration is required. Please see this page for more information about the workshop and symposium, as well as how to apply for registration.

Project personnel

Senior Personnel:

Tandy Warnow, UT-Austin. Overall project director
C. Randal Linder, UT-Austin.
Mark Holder, University of Kansas.
Jim Leebens-Mack, University of Georgia.
Etsuko Moriyama, University of Nebraska.
Webb Miller, Penn State University
Usman Roshan, New Jersey Institute of Technology
Michael Braun, Smithsonian Institute

Current and former students and postdocs

Siavash Mirarab, UT-Austin, PhD student of Tandy Warnow
Nam Nguyen, UT-Austin, PhD student of Tandy Warnow
Jeet Sukumaran, University of Kansas, PhD student of Mark Holder
Jiaye Yu, University of Kansas, PhD student of Mark Holder
Derrick Zwickl, University of Kansas, postdoctoral fellow of Mark Holder (now postdoc at the University of Arizona)
Cory Strope, University of Nebraska, PhD student and postdoc of Etsuko Moriyama (now postdoc of Jeff Thorne at North Carolina State University)
Catherine Anderson, University of Nebraska, PhD student of Etsuko Moriyama
Michael McKain, PhD student at the University of Georgia, of Jim Leebens-Mack
Daniel Money, postdoc of Mark Holder at the University of Kansas
Jamie Oaks, PhD student of Mark Holder at the University of Kansas.
Sarah Kingston, PhD student of Mike Braun at the Smithsonian Institution.

News

The Science article was selected for the Faculty of 1000 Biology.
Seed Magazine, article by Joe Kloc
Genome Web Daily News, article by Andrea Anderson.
Science Daily
Science Magazine, article by Loytyoja and Goldman.
The Skeptic's Guide to the Universe, where we are one of the possible science fiction stories.

Benchmark Datasets

Please see this page for benchmark datasets enabling testing of methods for estimating multiple sequence alignments, phylogenetic trees, supertrees, and phylogenetic placements of short metagenomic reads.

Software

SATé

GARLI: Genetic Algorithms for Rapid Likelihood Inference, developed by Derrick Zwickl.

SuperFine, a new supertree method, developed by Shel Swenson, Rahul Suri, C. Randal Linder, and Tandy Warnow.

FastSP: a fast method for comparing two multiple sequence alignments, developed by Siavash Mirarab and Tandy Warnow.

SEPP: SATé-enabled phylogenetic placement, developed by S. Mirarab, N. Nguyen, and T. Warnow.

indel-Seq-Gen, developed by Cory L. Strope.

SuiteMSA, visual tools for multiple sequence alignment comparison and molecular sequence simulation. Developed by C.L. Anderson, C.L. Strope, and E.N. Moriyama.

Other software:

Probtree (see "The effect of the guide tree on multiple sequence alignments and subsequent phylogenetic analyses"). This is a variant of ProbCons which uses a particular guide tree in order to improve the alignment and also the topological accuracy of the ML tree on the alignment. (Not publically available, but contact us on how to run this.)

Publications

In press

Liu, K. and T. Warnow. Treelength optimization for phylogeny estimation. To appear, PLoS One.
Neves, D. T., T. Warnow, J. L. Sobral and K. Pingali. Parallelizing SuperFine. To appear, 27th Symposium on Applied Computing (ACM-SAC), Bioinformatics, 2012 (PDF).
Liu, K., T.J. Warnow, M.T. Holder, S. Nelesen, J. Yu, A. Stamatakis, and C.R. Linder. "SATe-II: Very Fast and Accurate Simultaneous Estimation of Multiple Sequence Alignments and Phylogenetic Trees." (PDF), Systematic Biology, 61(1):90-106, 2011.
Bayzid, Md. S. and T. Warnow. "Finding Optimal Species Trees from Incomplete Gene Trees under Incomplete Lineage Sorting." To appear, Journal of Computational Biology
Liu, K. and T. Warnow. Treelength optimization for phylogeny estimation. To appear, PLoS One.
Swenson, M.S., R. Suri, C.R. Linder, and T. Warnow. "SuperFine: fast and accurate supertree estimation". In Press, Systematic Biology.
Neves, D. T., T. Warnow, J. L. Sobral and K. Pingali. Parallelizing SuperFine. To appear, 27th Symposium on Applied Computing (ACM-SAC), Bioinformatics, 2012.
McKain, M.R., N. Wickett, Y. Zhang, S. Ayyampalayam, W. R. McCombie, M. W. Chase, J. C. Pires, C. W. dePamphilis, and J. Leebens-Mack. 2012. Phylogenomic analysis of transcriptome data elucidates co-occurrence of a paleopolyploid event and the origin of bimodal karyotypes in Agavoideae (Asparagaceae). American Journal of Botany in press

2012

Mirarab, S., N. Nguyen, and T. Warnow. "SEPP: SATe-Enabled Phylogenetic Placement." Proceedings of the 2012 Pacific Symposium on Biocomputing (PDF).
Nguyen, N., S. Mirarab, and T. Warnow. MRL and SuperFine+MRL: new supertree methods." Journal Algorithms for Molecular Biology, 2012 (PDF).
Liu, K., C. Randal Linder, and T. Warnow. "RAxML and FastTree: Comparing Two Methods for Large-Scale Maximum Likelihood Phylogeny Estimation", PLoS One, 6(11): e27731. doi:10.1371/journal.pone.0027731

2011

Anderson, C.L., C. L. Strope, and E. N. Moriyama. Assessing Multiple Sequence Alignments Using Visual Tools. In Bioinformatics: Trends and Methodologies (ed. Mahdavi, M. A.). InTech (ISBN 978-953-307-282-1), 2011.
Mirarab, S. and T. Warnow. "FastSP: Linear-time calculation of alignment accuracy." Bioinformatics (2011) 27(23):3250-3258.
Liu, K., C. Randal Linder, and T. Warnow. "RAxML and FastTree: Comparing Two Methods for Large-Scale Maximum Likelihood Phylogeny Estimation." PLoS ONE 6(11): e27731. doi:10.1371/journal.pone.0027731
Yu, Y., T. Warnow, and L. Nakhleh. "Algorithms for MDC-based Multi-locus Phylogeny Inference." Proceedings of RECOMB 2011 (PDF).
Yu, Y., T. Warnow, and L. Nakhleh. Algorithms for MDC-Based Multi-Locus Phylogeny Inference: Beyond Rooted Binary Gene Trees on Single Alleles, J. Computational Biology, November 2011, Vol. 18, No. 11, pp 1543-1559 JCB.
Yang, J. and T. Warnow "Fast and accurate methods for phylogenomic analyses". RECOMB-CG 2011, and BMC Bioinformatics 12(Suppl 9): S4 (5 October 2011)
Anderson, C.L., C. L. Strope, and E. N. Moriyama (2011) SuiteMSA: Visual Tools for Multiple Sequence Alignment Comparison and Molecular Sequence Simulation. BMC Bioinformatics 12:184.

2010

Bradner, J.E., N. West, M.L. Grachan, E. Greenberg, S.J. Haggarty, T. Warnow and R. Mazitschek. "Chemical phylogenetics of histone deacetylases", 2010. Nature Chemical Biology. 6, pp. 238-243; published online 7 February 2010.
Swenson, M.S., F. Barbancon, C.R. Linder, and T. Warnow. "A simulation study comparing supertree and combined analysis methods using SMIDGen." Algorithms for Molecular Biology, 2010, 5:8 (4 January 2010), special issue of selected papers from WABI 2009. (PDF)
Ratan A, Zhang Y, Hayes VM, Schuster SC, Miller W. 2010. Calling SNPs without a reference sequence. BMC Bioinformatics 11: 130.
Schuster S.C., Miller W., Ratan A., Tomsho L.P., Giardine B., Kasson L.R., Harris R.S., Petersen D.C., Zhao F., Qi J., Alkan C., Kidd J.M., Sun Y., Drautz D.I., Bouffard P., Muzny D.M., Reid J.G., Nazareth L.V., Wang Q., Burhans R., Riemer C., Wittekindt N.E., Moorjani P., Tindall E.A., Danko C.G., Teo W.S., Buboltz A.M., Zhang Z., Ma Q., Oosthuysen A., Steenkamp A.W., Oostuisen H., Venter P., Gajewski J., Zhang Y., Pugh B.F., Makova K.D., Nekrutenko A., Mardis E.R., Patterson N., Pringle T.H., Chiaromonte F., Mullikin J.C., Eichler E.E., Hardison R.C., Gibbs R.A., Harkins T.T., Hayes V.M. (2010) Complete Khoisan and Bantu genomes from southern Africa. Nature 463:943-7.
Swenson, M.S., R. Suri, C.R. Linder, and T. Warnow. "An experimental study of Quartets MaxCut and other supertree methods." Journal of Algorithms for Molecular Biology 2010, special issue of selected papers from WABI 2010. See (PDF) for the earlier (incomplete) version of this paper.
Linder, C.R., R. Suri, K. Liu, and T. Warnow. "Benchmark datasets and software for developing and testing methods for large-scale multiple sequence alignment and phylogenetic inference." PLoS Currents: Tree of Life, 2010. Available at knol.google.com, here.
Liu, K., C.R. Linder, and T. Warnow. "Multiple sequence alignment: a major challenge for large-scale phylogenetics." PLoS Currents: Tree of Life, 2010. Available on knol.google.com, here.

2009

Liu, K., S. Nelesen, S. Raghavan, C.R. Linder, and T. Warnow. Barking up the wrong treelength: The impact of gap penalty on alignment and tree accuracy. IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol. 6, no. 1, pp. 7-21, Jan.-Mar. 2009, doi:10.1109/TCBB.2008.63
Liu, K., S. Raghavan, S. Nelesen, C. R. Linder, T. Warnow. Rapid and Accurate Large-Scale Coestimation of Sequence Alignments and Phylogenetic Trees. Science, vol. 324, no. 5934, pp. 1561-1564, 19 June 2009, doi: 10.1126/science.1171243. See the bottom of this page for a link to the paper.
Wang, Li-San, Jim Leebens-Mack, P. Kerr Wall, Kevin Beckmann, Claude W. de Pamphilis, and Tandy Warnow. The impact of multiple protein sequence alignment on phylogenetic estimation. IEEE Transactions on Computational Biology and Bioinformatics (TCBB), epub 01 Sept. 2009.
Strope, C.L., K. Abel, S.D. Scott, and E.N. Moriyama. Biological Sequence Simulation For Complex Evolutionary Hypotheses with indel-Seq-Gen version 2. Molecular Biology and Evolution, (2009), 26:2581-2593.
Strope, C.L., S.D. Scott, and E.N. Moriyama. Simulating sequence superfamilies for biological hypothesis testing. Proc. Biotechnology and Bioinformatics Symposium (BIOT-2009), pp. 69--70.
Swenson, M.S., F. Barbancon, R. Linder, and T. Warnow. "A simulation study comparing supertree and combined analysis methods using SMIDGen." Proceedings of WABI (Workshop on Algorithms for Bioinformatics) 2009.

2008

Nelesen, S., K. Liu, D. Zhao, C. R. Linder, and T. Warnow. The Effect of the Guide Tree on Multiple Sequence Alignments and Subsequent Phylogenetic Analyses. Pacific Symposium on Biocomputing 13:15-24, 2008. Auxiliary materials available here. Paper available in (PDF) form.
Holder, M.T., J. Sukumaran, and P.O. Lewis. A justification for reporting majority-rule consensus tree in Bayesian phylogenetics. Systematic Biology, (2008), 57(5):814-821.
Holder, M.T., D.J. Zwickl, C. Dessimoz. Evaluating the robustness of phylogenetic methods to among-site variability in substitution processes. Philosophical Transactions of the Royal Society B-Biological Sciences vol. 363, (2008), p. 4013., doi: 10.1098/rstb.2008.016.