Collaborative Research: ITR/AP Reconstructing Complex Evolutionary Histories

EIA-0121377

Moret, Bernard M

University of New Mexico

Collaborative Research: ITR/AP: Reconstructing Complex Evolutionary Histories

Reconstruction of the evolutionary history of a group of organisms has changed the face of biology and is being used increasingly in drug discovery, epidemiology, and genetic engineering. Unfortunately, such reconstructions typically involve solving difficult optimization problems, so that even moderately large datasets can require months to years of computation. In addition, almost all evolutionary reconstructions presently assume that the historical pattern is one of strict divergence that can be represented by a binary tree. This assumption is frequently violated, especially by plants which often hybridize readily and thus produce networks of relationships.

This project brings together computer scientists and biologists from two institutions to develop new models and algorithms to address these two problems. Successful completion of this project will have an enormous impact by providing tools for reconstructing phylogenies of large datasets, and the first tools for inferring network models of evolution appropriate to hybridizing speciation. Such network models will alter how biologists think about speciation, while the development of methods for large-scale analyses will strongly benefit medical and pharmaceutical practice.

Information technology will be advanced in fundamental ways as well, as the project will demonstrate how algorithm design and high-performance algorithm engineering can jointly solve very difficult discrete optimization problems.