NSF Funds Evolutionary History Research
September 13, 2019Share story
Ran聽Libeskind-Hadas, R. Michael Shanahan Professor of Computer Science, studies algorithmic issues in computational biology鈥攊n 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.
鈥淣ew 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. 鈥淚n 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, 鈥淔inding 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, 鈥淩UI: Algorithms and Tools for Phylogenetic Tree Reconciliation.鈥�
鈥淲e explored problems related to phylogenetic tree reconciliation, including proving the intractability of certain problems and development of efficient algorithms for others,鈥� he says. 鈥淭his 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.鈥�