ITR/AP(DEB): Collaborative Research `Computing Optimal Phylogenetic Trees under Genome Rearrangement Metrics'

University Of New Mexico, Albuquerque NM

Investigators

Abstract

ABSTRACT PI Jansen - #0113654 PI Moret - #0113095 This award provides support for a collaborative project between two biologists (Jansen and Boore) and three computer scientists (Moret, Warnow, and Bader) to develop and test new algorithms and software for constructing evolutionary trees (phylogenies) from the rapidly increasing amount of genomic data. The estimation of phylogenies is crucial to a wide range of basic and applied biological problems such as the epidemiology of AIDS, the identification of viral agents, the analysis of protein structure and function, the prediction of RNA structure; and, of course, it is the basic tool for inferring evolutionary history. Methods for the reconstruction of phylogenies are most commonly applied to DNA sequences. In many cases these sequences change at rates that are too low or too high for recovering accurate evolutionary trees. One new type data that is fast gaining favor in the biology community is gene order and content within whole genomes, but so far very few computational methods have been developed for these types of data. The three goals of the project are to: (1) develop algorithms and software for reconstructing evolutionary trees from gene order and content data; (2) assess the performance of these algorithms through extensive simulation studies under parameter-rich models of genome evolution and through application to real datasets; and (3) develop high-performance implementations of the best algorithms designed in the project using algorithm engineering techniques and a flexible approach to parallelization. This project will make significant contributions in biology, through the development of new models of genome evolution and an improved understanding of the evolution of chloroplast and mitochondrial genomes, and in computer science, through the development and testing of new algorithms for genomic data and the application of high-performance computing to problems in phylogenetic analysis.