SODA Conference 2008 Conference Paper
Fast and reliable reconstruction of phylogenetic trees with very short edges
- Ilan Gronau
- Shlomo Moran
- Sagi Snir
Author name cluster
Ilan Gronau
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
2 papers
2 author rows
Possible papers
2TCS Journal 2007 Journal Article
On the hardness of inferring phylogenies from triplet-dissimilarities
- Ilan Gronau
- Shlomo Moran
This work 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 ℓ ∞ norm. 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. On the positive side, we present a polynomial time constant-rate approximation algorithm for this problem. 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.