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)

Document last modified on September 20, 1995