III: Small: RUI: Finding Best Representative Phylogenetic Tree Reconciliations

该项目将开发新的技术和软件工具，以帮助生物学家研究寄生虫及其宿主生物体等群体之间的关系。 这些方法和工具将使生命科学家能够更好地了解病毒和细菌疾病的起源，攻击作物的寄生虫以及其他成对的共同进化群体。 该项目将涉及新算法的设计和分析，在大型生物数据集上系统验证这些算法，以及开发一个将广泛传播的软件工具。 这项工作将在一所本科学院进行，并将为大约25名学生从事研究做好准备。 这项工作还将为高中生和大学生提供教材和推广活动。该奖项下的工作将探索协调代表宿主和寄生虫或基因和物种等分类群的系统发育树对的问题。 给定一对系统发育树和它们的叶子之间的关联，最大简约调和试图映射一棵树（例如，寄生树）到另一个（例如，宿主物种树），以尽量减少解释其不一致性所需的生物事件的数量。 一般来说，这种最大简约调和的数量可以随着树的大小呈指数增长。 因此，很难或不可能确定一个或少数最具代表性的调节。 这项工作将开发有效的算法，以找到最具代表性的和解，以使更强大的结论对类群的进化历史。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

This project will develop new techniques and software tools to aid biologists in studying the relationships between groups such as parasites and their host organisms. These methods and tools will allow life scientists to better understand the origins of viral and bacterial diseases, parasites that attack crops, and other pairs of co-evolving groups. The project will involve the design and analysis of new algorithms, systematic validation of these algorithms on large biological datasets, and the development of a software tool that will be broadly disseminated. This work will be conducted at an undergraduate college and will prepare approximately 25 students to engage in research. The work will also result in teaching materials and outreach activities for high school and college students.The work under this award will explore the problem of reconciling pairs of phylogenetic trees representing taxa such as hosts and parasites or genes and species. Given a pair of phylogenetic trees and the associations between their leaves, maximum parsimony reconciliation seeks to map one tree (e.g., the parasite tree) onto the other (e.g., the host species tree) to minimize the number of biological events required to explain their discordance. In general, the number of such maximum parsimony reconciliations can grow exponentially with the size of the trees. Consequently, it can be difficult or impossible to identify one, or a small number, of best representative reconciliations. This work will develop efficient algorithms to find best representative reconciliations in order to make more robust conclusions about the evolutionary histories of the pairs of taxa. These algorithms will be implemented in a new software tool for life science researchers.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.