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

Claremont Mckenna College, Claremont CA

Investigators

Abstract

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.