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

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

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.