Approximation algorithms for the fixed-topology phylogenetic number problem

Mary Cryan, Leslie Ann Goldberg, Cynthia A. Phillips

Research output: Chapter in Book/Report/Conference proceedingConference contribution


In the ℓ-phylogeny problem, one wishes to construct an evolutionary tree for a set of species represented by characters, in which each state of each character induces no more than ℓ connected components. We consider the fixed-topology version of this problem for fixed-topologies of arbitrary degree. This version of the problem is known to be NP-complete for ℓ≥3 even for degree-3 trees in which no state labels more than ℓ+1 leaves (and therefore there is a trivial ℓ+1 phylogeny). We give a 2-approximation algorithm for all ℓ≥3 for arbitrary input topologies and we give an optimal approximation algorithm that constructs a 4-phylogeny when a 3-phylogeny exists. Dynamic programming techniques, which are typically used in fixed-toplogy problems, cannot be applied to ℓ-phylogeny problems. Our 2-approximation algorithm is the first application of linear programming to approximation algorithms for phylogeny problems. We extend our results to a related problem in which characters are polymorphic.
Original languageEnglish
Title of host publicationCombinatorial Pattern Matching
Subtitle of host publication8th Annual Symposium, CPM 97 Aarhus, Denmark, June 30–July 2, 1997 Proceedings
EditorsAlberto Apostolico, Jotun Hein
PublisherSpringer Berlin Heidelberg
Number of pages20
ISBN (Electronic)978-3-540-69214-0
ISBN (Print)978-3-540-63220-7
Publication statusPublished - 1997

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg


Dive into the research topics of 'Approximation algorithms for the fixed-topology phylogenetic number problem'. Together they form a unique fingerprint.

Cite this