无忧视频

Student Lauded for Computational Biology Research

Students studying evolutionary biology at 无忧视频 are learning about phylogenetic tree reconciliation, a computational method used to reconstruct the evolutionary histories of related pairs of organisms, such as hosts and parasites, or species and gene families. Work in this area earned Jordan Haack 鈥�19 a Best Student Paper award at an international conference.

Haack, who enjoys using algorithms to solve computational biology problems, received the award at the 2018 Asia-Pacific Bioinformatics Conference in Yokohama, Japan, for the paper 鈥淐omputing the Diameter of the Space of Maximum Parsimony Reconciliations in the Duplication-Transfer-Loss Model鈥� on which he was the first author. Along with Harvey Mudd computer science professors Yi-Chieh (Jessica) Wu and Ran Libeskind-Hadas and fellow research students Eli Zupke (Cal Poly Pomona) and Andrew Ramirez (Caltech), Haack demonstrated a fast, polynomial-time algorithm that helps to measure differences between two evolutionary trees and compute them efficiently.

鈥淭he overall goal of the problem is to take as input two trees and a set of associations between their leaves, and output a mapping between the trees that minimizes the cost of implied evolutionary events,鈥� Haack explains. 鈥淥ur research focused on the duplication-transfer-loss (DTL) model, which is widely used, and covers four biological events: speciation, duplication, transfer and loss. Previous publications have computed sets of cost, minimizing reconciliations in polynomial time. Notably, there can potentially be an exponential number of maximum parsimony reconciliations (MPRs) with respect to the sizes of the gene and species trees.鈥�

The researchers sought to compute the 鈥渄iameter鈥� of this space of maximum parsimony reconciliations. 鈥淭his diameter metric is useful because it helps a biologist characterize the space of MPRs,鈥� says Haack. 鈥淔or example, it may be the case that there are a large number of MPRs, but they only differ on a few events. Or, there may be a small number of MPRs, but they are mostly different.鈥�

鈥淭his paper provides some new insights into a well-known problem that arises in computational biology,鈥� says Libeskind-Hadas, R. Michael Shanahan Professor of Computer Science. 鈥淭he problem arises, for example, when trying to understand the evolutionary histories of a gene family and the species聽in which the genes are found.聽While there exist good algorithms for finding mappings between two such evolutionary 鈥榯rees,鈥� it鈥檚 been known for some time that the number of 鈥榞ood鈥� mappings can be extremely large, much too large to examine them all.聽So, an open question has been:聽When there are many equally good mappings between two evolutionary trees, how different are all of those mappings? This work is likely to provide biologists with new insights into large datasets that they previously didn鈥檛 have.鈥�

Libeskind-Hadas says that Haack made key contributions to this work, both in developing the algorithms and implementing and testing them on real datasets.

Libeskind-Hadas and Wu are continuing to work with students on a number of problems related to algorithms and software tools for phylogenetic tree reconciliation. Their work is supported by internal funds and grants from the National Science Foundation.