Wednesday, October 24, 2001
Hewlett Packard Auditorium, 306 Soda Hall
4:00-5:00 p.m.

Dr. Tandy Warnow

Computer Science Department, University of Texas at Austin CRA Distinguished Lecture

Computational Problems in Evolutionary Tree Reconstruction

Abstract:

Phylogenetic trees, also known as evolutionary trees, model the evolution of biological species or genes from a common ancestor. Reconstructing evolutionary trees is a fundamental research problem in biology, with applications to protein structure and function prediction, pathway detection, sequence alignment, drug design, etc. However, the reconstruction of very large evolutionary trees is exceedingly difficult; not only are the major optimization problems NP-hard, but large real datasets of interest to the biological community can take years of analysis without being solved exactly. Furthermore, while polynomial time methods for phylogeny reconstruction exist, our research shows that the standard approaches (including the popular Neighbor Joining method) may have "large sequence length requirements". In this talk I will describe the progress our group is making for both types of difficulties. In particular, I will describe new dataset decomposition techniques, called Disk-Covering, which can be used in conjunction with any phylogenetic method. We can prove theoretical performance guarantees, with respect to the sequence length required for accuracy, and we can demonstrate improvements in performance with respect to the running time of algorithms for NP-hard optimization problems, such as maximum parsimony and maximum likelihood.

If time permits, I will also present results on our research into inferring evolutionary trees from whole genomes.