On Oct 5, 2005, PED Seminar Series Presents

Inferring Evolutionary Histories by Likelihood Methods: Computational Hardness

by Sébastien Roch

Maximum likelihood is a widely used technique for reconstructing phylogenies from molecular sequences. A shortcoming of the approach is that it appears to be highly demanding computationally. However, until recently, it remained a long-standing open problem in computational biology to provide a theoretical understanding of the computational complexity of this technique. In this talk, I will sketch a short proof that phylogenetic reconstruction by maximum likelihood is indeed NP-hard and that it is in fact hard to approximate. I will use some recent results from computer science as well as a connection to parsimony.

View Slides

View his homepage

upcoming PED seminars