DIMACS Seminar on Math and CS in Biology


Approximating the Most Likely Tree Efficiently


Sampath Kannan
Department of Computer Science
University of Pennsylvania


CoRE Building, Room 431
Busch Campus, Rutgers University


1:00 PM
Tuesday, September 26, 1995


The maximum likelihood method is the method of choice for phylogeny construction but it is computationally very hard.

In this talk we will describe a simple and efficient algorithm that converges to the most likely tree. Moreover the convergence rate of this algorithm is almost as good as the information-theoretic lower bound that we establish. To our knowledge this is the first efficient algorithm that is provably consistent for phylogeny construction.

(joint work with Martin Farach)

Document last modified on September 20, 1995