Skip to content

PLG

Seminar

On the hardness of inferring Phylogenies from triplet-dissimilarities

Moran, S (Technion)
Monday 17 December 2007, 14:40-15:00

Seminar Room 1, Newton Institute

Abstract

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.

Presentation

[ppt ]

Audio

MP3MP3

Video

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.

Back to top ∧