Intellectual Merit. The main focus of this project was the development of new algorithms with provable theoretical guarantees for estimating evolutionary trees (also called "phylogenies"). We specifically examined methods that can address genome-scale phylogeny estimation, which is complicated by biological processes, such as incomplete lineage sorting (ILS) and gene duplication and loss (GDL), that can cause the evolutionary trees for single genes to be different from that of the species tree.  Current evolutionary biology projects often seek to estimate species trees with hundreds of species and thousands or tens of thousands of genes, and standard methods, such as using maximum likelihood methods applied to the concatenated gene sequences, do not have good theoretical performance guarantees.  For this reason, new methods are needed that have theoretical performance guarantees (such as being statistically consistent, and so proven to recover the true species tree with high probability given enough data) and have good accuracy in practice. This was a main goal of our project. 

For species tree estimation addressing ILS, our research group developed several new methods with excellent theoretical and empirical advantages over current leading methods. Among the highlights of this effort, we developed ASTRID (Vachaspati and Warnow, BMC Genomics 16.S10 (2015): S3), a polynomial time method for species tree estimation that addresses incomplete lineage sorting (ILS) and is faster than any of the current available methods on large and ultra-large datasets, with 10,000 species and genes.  We proved the surprising result that partitioned analyses using maximum likelihood on multi-locus datasets can be positively misleading and so converge to the wrong species tree as the number of genes increases (Roch et al., Systematic Biology 68.2 (2019): 281-297).  In Legried et al., RECOMB 2020, we proved that ASTRAL-multi (Rabiee et al., Molecular Phylogenetics and Evolution 130 (2019): 286-296), a species tree estimation method to address ILS, is statistically consistent in the presence of gene duplication and loss (GDL); this was the first method proven statistically consistent under GDL.

Another major effort was to develop general purpose methods for scaling computationally intensive methods to large datasets. This is important because many of the most accurate methods are based on hard optimization problems, and so can be computationally intensive on large datasets (and infeasible on even moderately large datasets).  Therefore, we developed approaches based on divide-and-conquer. These "meta-methods" apply computationally intensive methods on small subsets of the species, and then combine the subset trees together. For the case where the subset trees are overlapping, we developed new supertree methods, with FastRFS (Vachaspati and Warnow, Bioinformatics  33.5 (2017): 631-639) a particularly powerful technique: it finds an exact solution to a hard optimization problem within a constrained search space, and does so in polynomial time. FastRFS improves on the prior best methods for the popular Robinson-Foulds Supertree Problem. For the case where the subset trees are disjoint, we developed methods that use auxiliary information to combine these disjoint subset trees, and are proven to maintain the desirable statistical guarantees of their base methods and to run in polynomial time. Two of the major advances include TreeMerge (Molloy and Warnow, Bioinformatics 35.14 (2019): i417-i426) and the Guide Tree Merger (Smirnov and Warnow, BMC Genomics 21 (2020): 1-17).  We showed that GTM and TreeMerge maintain accuracy and greatly reduce the running time of existing methods for species tree estimation, especially on large datasets.  

Broader Impacts: We provided open-source software for new methods in phylogeny estimation and trained biologists in the use of these software packages at national and international meetings. Three PhD students and two MS students graduated and were supported by this project.  The methods we developed are now being used in phylogenomic projects. 

Last Modified: 11/01/2020
Modified by: Tandy Warnow