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

从不断增长的进化信息库中合成数千个物种的进化树不仅有益于整个生物学，而且对科学和整个社会都有着巨大的希望。例如，大规模进化树的预测能力在引领人类健康进步、增加农业生产以及为自然资源管理决策提供信息方面发挥着重要作用。尽管有这些承诺，但从遗传数据推断如此巨大的树正面临着计算生物学社区面临的当今进化生物学中最具挑战性和最复杂的计算问题。采油树装配问题已成为解决这些挑战的有力工具。该项目研究这样的问题，即在给定一组通常较小的进化树的情况下，寻找一棵组合树来协调这些输入树中的总体冲突。这种冲突通常通过特定于问题的树比较措施来衡量。这些度量的数学和计算性质在组合树的高效计算、可信度和分析中起着至关重要的作用，因此是该项目的研究重点。将利用系统发育数据库提供的数据，在实践中分析在该项目中开发的方法的可扩展性和准确性。研究成果将在计算生物学和进化生物学社区内广泛传播。通过该项目提供的研究生和本科生培训机会将通过广泛的跨学科合作，通过获得进化生物学中生物学、数学和算法挑战的平衡视角，丰富学生的教育经验。未被充分代表的少数族裔将通过在爱荷华州立大学致力于这类少数群体的生物信息学项目中的演讲，通过轮换和研究助理奖学金将少数族裔学生纳入该项目，并通过爱荷华州立大学的公共活动，如主要交易会或学生组织的生物信息学和计算生物学研讨会，吸引少数族裔学生进入计算生物学和生物信息学领域。该项目还将在爱荷华州立大学为K-12年级的学生举办计算思维研讨会，涉及计算生物学和生物信息学的主题。开发的方法将使生物学家能够组装更大、更可信的进化树。这些方法处理无根和可能错误的进化树的能力将在很大程度上扩展到它们在实践中的适用性。进化树的组装通常依赖于比较度量及其最大可能距离，称为直径。识别树木比较测量的直径并有效地计算这些直径将允许补偿形状偏差，这些偏差可能从根本上改变树木组装方法的结果。对于几个比较指标，只有它们的直径的弱上限是已知的，研究将调查收紧这些界限。组装方法的识别特性将支持生物学家艰难地选择合适的组装方法。这样的性质还将导致树组装方法的有效可解实例的数学表征和参数化。新的线性时间算法提供了在各种树比较措施下对所有可能的根的评估，将支持生物学家准确地识别这种根的挑战性任务。最后，本研究的理论结果将为树的组装和比较系统发育提供算法基础。

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.