NSF Funds Computer Science Research in Evolutionary Biology

Pairings of interacting organisms, like parasites and their hosts, interact in complex ways. A Harvey Mudd team of computational biologists seeking to better understand these interactions has received grant funding from the National Science Foundation. Ran Libeskind-Hadas, R. Michael Shanahan Professor of Computer Science and chair of the Computer Science Department, was awarded a continuing three-year grant for his proposal titled “Algorithms and Tools For Phylogenetic Tree Reconciliation.”

Phylogenetic tree reconciliation is a computational method used to reconstruct the evolutionary histories of related pairs of organisms by hypothesizing the evolutionary events that explain their incongruence. For example, parasites and their hosts co-evolve through processes like speciation, host switch and extinction. Phylogenetic reconciliation attempts to infer the most likely scenario in which two organisms co-evolved under these events. These analyses can be used to identify important specific events—for example, a host switch of a virus from one primate lineage to another—and to perform various kinds of statistical analyses.

“Understanding these complex interactions is both important for the advancement of basic science and for discoveries that contribute to human health and the long-term health of our environment,” says Libeskind-Hadas. “Our work seeks to find the best-supported histories of pairs of phylogenies by identifying the evolutionary events that link them.”

Libeskind-Hadas’ research combines algorithm design, visualization methods and the development of practical software tools. Libeskind-Hadas and his team have already contributed to these efforts by proving results on the computational complexity of tree reconciliation, developing efficient algorithms for key problems and using those algorithms as the bases for practical software tools. The team’s results have been implemented in its own widely used Jane software, an algorithmic tool designed specifically for cophylogenetic reconstruction.

The work involves a large number of Harvey Mudd undergraduates and offers them a compelling opportunity to see a facet of research in computational biology. In keeping with the College’s vision for diversity, a stated goal of the project is to involve those from traditionally underrepresented groups.

Libeskind-Hadas says this work will advance scientific knowledge as researchers develop new algorithms, new methods for summarizing and visualizing large numbers of different tree reconciliations, and new software tools that facilitate fundamental biology research.

“We hope the results will provide new tools for researchers addressing a broad set of issues that ultimately relate to health, sustainability and fundamental questions in evolutionary biology.”