Students studying evolutionary biology at Harvey Mudd College 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 \u201919 a Best Student Paper award at an international conference.<\/p>\n
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 \u201cComputing the Diameter of the Space of Maximum Parsimony Reconciliations in the Duplication-Transfer-Loss Model\u201d 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.<\/p>\n
\u201cThe 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,\u201d Haack explains. \u201cOur 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.\u201d<\/p>\n
The researchers sought to compute the \u201cdiameter\u201d of this space of maximum parsimony reconciliations. \u201cThis diameter metric is useful because it helps a biologist characterize the space of MPRs,\u201d says Haack. \u201cFor 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.\u201d<\/p>\n
\u201cThis paper provides some new insights into a well-known problem that arises in computational biology,\u201d says Libeskind-Hadas, R. Michael Shanahan Professor of Computer Science. \u201cThe problem arises, for example, when trying to understand the evolutionary histories of a gene family and the species\u00a0in which the genes are found.\u00a0While there exist good algorithms for finding mappings between two such evolutionary \u2018trees,\u2019 it\u2019s been known for some time that the number of \u2018good\u2019 mappings can be extremely large, much too large to examine them all.\u00a0So, an open question has been:\u00a0When 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\u2019t have.\u201d<\/p>\n
Libeskind-Hadas says that Haack made key contributions to this work, both in developing the algorithms and implementing and testing them on real datasets.<\/p>\n
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.<\/p>\n","protected":false},"excerpt":{"rendered":"
Students studying evolutionary biology at Harvey Mudd College are learning about phylogenetic tree reconciliation, a computational method used to reconstruct […]<\/p>\n","protected":false},"author":47,"featured_media":6291,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[3,11,26,30],"class_list":["post-6290","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-award","category-computer-science","category-research","category-students"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.hmc.edu\/about\/wp-json\/wp\/v2\/posts\/6290","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.hmc.edu\/about\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.hmc.edu\/about\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.hmc.edu\/about\/wp-json\/wp\/v2\/users\/47"}],"replies":[{"embeddable":true,"href":"https:\/\/www.hmc.edu\/about\/wp-json\/wp\/v2\/comments?post=6290"}],"version-history":[{"count":0,"href":"https:\/\/www.hmc.edu\/about\/wp-json\/wp\/v2\/posts\/6290\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.hmc.edu\/about\/wp-json\/wp\/v2\/media\/6291"}],"wp:attachment":[{"href":"https:\/\/www.hmc.edu\/about\/wp-json\/wp\/v2\/media?parent=6290"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.hmc.edu\/about\/wp-json\/wp\/v2\/categories?post=6290"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}