Finding the closest ultrametric

Marco Di Summa, David Pritchard, Laura Sanità

Research output: Contribution to journalArticleAcademicpeer-review

5 Citations (Scopus)

Abstract

Ultrametrics model the pairwise distances between living species, where the distance is measured by hereditary time. Reconstructing the tree from the ultrametric distance data is easy, but only if our data is exact. We consider the NP-complete problem of finding the closest ultrametric to noisy data, as modeled by multiplicative or additive total distortion, with or without a monotonicity assumption on the noise. We obtain approximation ratio O(logn) for multiplicative distortion where n is the number of species, and O(1+(ρ-1)-1) for additive distortion where ρ is the minimum ratio of any two distinct input distances. As part of proving our approximation bound for additive distortion, we give the first constant-factor approximation algorithm for a previously-studied problem called Cluster Deletion.

Original languageEnglish
Pages (from-to)70-80
Number of pages11
JournalDiscrete Applied Mathematics
Volume180
DOIs
Publication statusPublished - 10 Jan 2015
Externally publishedYes

Keywords

  • Approximation algorithm
  • Cluster deletion
  • Phylogenetic reconstruction
  • Ultrametric

Fingerprint Dive into the research topics of 'Finding the closest ultrametric'. Together they form a unique fingerprint.

Cite this