DIMACS Seminar on Math and CS in Biology


Title:

Approximating the Most Likely Tree Efficiently

Speaker:

Sampath Kannan
Department of Computer Science
University of Pennsylvania

Place:

CoRE Building, Room 431
Busch Campus, Rutgers University

Time:

1:00 PM
Tuesday, September 26, 1995

Abstract:

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)


dimacs-www@dimacs.rutgers.edu
Document last modified on September 20, 1995