NSF Funds Evolutionary History Research

Ran Libeskind-Hadas, R. Michael Shanahan Professor of Computer Science, studies algorithmic issues in computational biology—in particular, the problem of phylogenetic tree reconciliation, a computational method used to reconstruct the evolutionary histories of related pairs of organisms by hypothesizing the evolutionary events that explain their incongruence. The reconciliation is a mapping of one tree onto the other that seeks to explain the evolutionary history of the pair with respect to a biological model.

“New computational methods and tools are needed to provide biologists with a summary of maximum parsimony reconciliation (MPR) space by identifying the best representative MPRs and statistics that quantify how well these representative MPRs summarize the space,” says Libeskind-Hadas. “In general, no single MPR can adequately represent the entire set of optimal solutions. Making inferences from a single MPR may lead to conclusions that are not supported, or even contradicted, by other equally optimal solutions.”

The National Science Foundation (NSF) has awarded a grant of $498,458 for support of Libeskind-Hadas’ research and the design, analysis and empirical evaluation of algorithms leading to transformative new tools for biologists. Funding will support six research students a year for three years, beginning summer 2020, as well as travel to conferences. It will also fund the purchase of a high-performance computer to test the algorithms and perform computational experiments.

The project, “Finding Best Representative Phylogenetic Tree Reconciliations,” seeks to develop efficient algorithms for systematically identifying a small set of the most representative MPRs. Results will be extended to deal with the larger solution spaces induced by a range of event costs and for non-binary trees. This will allow development of new software for life scientists and the ability to generalize these results to event models beyond the duplication-transfer-loss model.

Libeskind-Hadas performed precursory research for this project in a previous NSF-funded project, “RUI: Algorithms and Tools for Phylogenetic Tree Reconciliation.”

“We explored problems related to phylogenetic tree reconciliation, including proving the intractability of certain problems and development of efficient algorithms for others,” he says. “This work addressed some foundational problems in tree reconciliation and also established the foundations for the current project by demonstrating that a single MPR generally does not suffice to represent MPR space, by developing algorithmic methods that will be useful in finding representative sets, and by collaborating with end-users to understand the needs for the next generation of reconciliation tools.”