AF:Small:Algorithmic Foundations for Evolutionary Tree Comparison and Assembly

Iowa State University, Ames IA

Investigators

Abstract

Synthesizing evolutionary trees for thousands of species from an ever-increasing pool of evolutionary information is not only beneficial throughout biology, but also holds enormous promise for science and society at large. For instance, the predictive power of large-scale evolutionary trees plays an important role in leading advances in human health, increasing agricultural production, and to inform decisions about natural resource management. Despite these promises, inferring such large trees from genetic data is confronting the computational biology community with the most challenging and complex computational problems in evolutionary biology today. Tree assembly problems have emerged as a powerful tool to address these challenges. The project investigates such problems that, given a collection of typically smaller evolutionary trees, seek an assembled tree that reconciles the overall conflict in these input trees. This conflict is often measured by a problem-specific tree comparison measure. Mathematical and computational properties of such measures play a critical role in the efficient computation, credibility, and analysis of assembled trees, and therefore, are the focal research point of the project. Scalability and accuracy of the methods developed in the project will be analyzed in practice using data provided by phylogenetic databases. Research results will be widely disseminated within the computational biology and evolutionary biology communities. Graduate and undergraduate training opportunities offered through the project will enrich the educational experience of students through extensive interdisciplinary collaborations by acquiring a balanced perspective of biological, mathematical, and algorithmic challenges in evolutionary biology. Underrepresented minorities will be engaged through presentations in the bioinformatics programs at Iowa State University dedicated to such minorities, incorporating minority students into the project through rotations and research assistantships, and by attracting minority students to the field of computational biology and bioinformatics through public events at Iowa State University, like Major Fairs, or the student organized Bioinformatics and Computational Biology Symposia. The project will also engage in computational thinking workshops at Iowa State University for K-12 students by involving topics in computational biology and bioinformatics. The developed methods will enable biologists to assemble larger and more credible evolutionary trees. The ability of these methods to handle unrooted and possibly erroneous evolutionary trees will largely extend on their applicability in practice. Evolutionary tree assembly often relies on comparison metrics and their largest possible distances, called diameters. Identifying diameters for tree comparison measures and computing these diameters efficiently will allow for compensation of shape-biases that can radically alter the outcome of tree assembly methods. For several comparison measures only weak upper bounds on their diameters are known, and the research will investigate into tightening these bounds. Identified properties of assembly methods will support biologists in their difficult choice of appropriate assembly methods. Such properties will also lead to mathematical characterizations and parameterizations of efficiently solvable instances of tree assembly methods. Novel linear time algorithms that provide evaluations of all possible rootings under various tree comparison measures will support biologists in their challenging task of identifying such rootings accurately. Finally, the theoretical results of the research will advance the algorithmic foundations of tree assembly and comparative phylogenetics.