Penn Arts & Sciences Logo

Penn Mathematics Colloquium

Wednesday, September 17, 2003 - 4:30pm

Tandy Warnow

University of Texas

Location

University of Pennsylvania

DRL A6

The program is made possible by a grant from the Fund to Encourage Women (FEW) of the Trustees' Council of Penn Women

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. One approach to the problem of reconstructing phylogenies is statistical; we model the evolutionary process that generates DNA sequences as a stochastic process, and we seek to infer the unknown tree from the sequences generated at the leaves of the tree. For many simple models of evolution, accurate reconstruction with arbitrarily high probability is guaranteed from finite sequence lengths, using appropriate methods; methods which have this guarantee are called "statistically consistent". However, only recently has there been any study of the sequence length requirement, as a function of the parameters of the model tree, a given method requires for accurate reconstruction with high probability. In this talk we will present the theory of "fast converging" methods, which are methods which can recover the true tree with high probability from sequences of length that grow polynomially in the number of leaves, for every way of fixing the range of edge "lengths". We will also present some experimental results showing the improvement in performance of the newest methods in this class over standard methods used in phylogenetic analysis.