• Calendar

March 29, Tuesday
12:00 – 14:00

Understanding the origin and evolution of extant and extinct species is a fundamental scientific quest. Today, phylogenetic trees are widely used as the accepted evolutionary model, and are mostly based upon molecular sequences (amino acid or DNA) data. The space of candidate trees grows exponentially with the number of species, implying that even on modern computers, an exhaustive search over all trees is infeasible (except for few species, no more than approximately 20).

Two reconstruction criteria most frequently used are maximum parsimony (MP), and maximum likelihood (ML). But are they solvable in a computationally efficient manner? Maximum parsimony (MP) was proved intractable almost 20 years ago (1986). The analogue question for maximum likelihood (ML) remained unsolved.

This created a strange situation, because most practitioners believe that ML is computationally harder than MP. Namely computer programs running on the same sets of sequences tend to take much longer to solve ML than MP. Yet ML remained ``unclassified'', leaving the existence of an efficient ML algorithm a possibility.

We resolve this question, and show that ML on phylogenetic trees is indeed computationally intractable (NP hard). Therefore, the reason why no ``magic bullet'', or efficient ML algorithm using clever algorithmic techniques was found, is because no such ``magic bullet'' exists.

This is joint work with Tamir Tuller.