Collaborative Research: ITR/AP Reconstructing Complex Evolutionary Histories

University Of Texas At Austin, Austin TX

Investigators

Abstract

EIA-0121680 Warnow, Tandy J University of Texas at Austin Collaborative Research: ITR/AP: Reconstructing Complex Evolutionary 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.