Professors Fernandez-Baca and Eulenstein were recently notified that their proposal, "Algorithmic Foundations of Phylogenetic Tree Reconciliation," has been funded by the National Science Foundation. The award is for a total of $450,000 over three years.
A phylogenetic tree represents the genealogy of a set of species. A major obstacle to assembling large phylogenetic trees reliably is the sparseness of the coverage provided by the available genomic data. That is, the same genetic information may not be at our disposal for all species. For example, a gene may not have been sequenced for a species of interest or the gene may simply be absent from that species. One approach to address this problem is to find a collection of overlapping subsets of the species, each of which has the property that similar genetic data is available for every species in the subset. A phylogenetic tree is built for each subset and then the trees are combined into a single supertree for the entire set of species. Building supertrees is nontrivial, as it involves reconciling conflicts among the various input trees with regard to the placement of certain species.
Professors Fernandez-Baca and Eulenstein will study the fundamental algorithmic questions that arise in reconciling multiple conflicting phylogenetic trees into a single supertree that represents them all. They will treat the reconciliation problem as one of finding a supertree whose total dissimilarity with the input trees is minimum. To this end, they will study a variety of measures. Some of these will be based purely on tree structure; for example, on what groupings a tree implies on its species set. They will also study measures that attempt to identify the possible occurrence of complex evolutionary events such as gene duplication and subsequent loss, and horizontal gene transfer. The work will benefit from Professor Fernandez-Baca and Eulenstein's longstanding collaboration with the evolutionary biology community. The results of the research will be widely disseminated within that community, where they could have significant implications for phylogenetic tree databases.