skip to content

On the hardness of inferring Phylogenies from triplet-dissimilarities

Monday 17th December 2007 - 14:40 to 15:00
INI Seminar Room 1
Session Chair: 
Kathi Huber

We considers the problem of reconstructing a phylogenetic tree from triplet dissimilarities, which are dissimilarities defined over taxon-triplets. Triplet dissimilarities are possibly the simplest generalization of pairwise dissimilarities, and were used for phylogenetic reconstructions in the past few years. We study the hardness of finding a tree best fitting a given triplet-dissimilarity table under the "maximal difference" criterion. We show that the corresponding decision problem is NP-hard and that the corresponding optimization problem cannot be approximated in polynomial time within a constant multiplicative factor smaller than 1.4. We also address the issue of best-fit under "maximal distortion", which corresponds to the largest ratio between matching entries in two triplet-dissimilarity tables. We show that it is NP-hard to approximate the corresponding optimization problem within any constant multiplicative factor. On the positive side, we present a polynomial time constant-rate approximation algorithm for this problem.

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons