Minimum-flip supertrees: Complexity and algorithms

Duhong Chen, Oliver Eulenstein, David Fernández-Baca, Michael Sanderson

Research output: Contribution to journalArticlepeer-review

32 Scopus citations


The input to a supertree problem is a collection of phylogenetic trees that intersect pairwise in their leaf sets; the goal is to construct a single tree that retains as much as possible of the information in the input. This task is complicated by inconsistencies due to errors. We consider the case where the input trees are rooted and are represented by the clusters they exhibit. The problem is to find the minimum number of flips needed to resolve all inconsistencies, where each flip moves a taxon into or out of a cluster. We prove that the minimum-flip problem is NP-complete, but show that it is fixed-parameter tractable and give approximation algorithms for special cases.

Original languageEnglish (US)
Pages (from-to)165-173
Number of pages9
JournalIEEE/ACM Transactions on Computational Biology and Bioinformatics
Issue number2
StatePublished - Apr 2006


  • NP-completeness
  • Phylogenetic tree
  • Supertree
  • Tree assembly

ASJC Scopus subject areas

  • Biotechnology
  • Genetics
  • Applied Mathematics


Dive into the research topics of 'Minimum-flip supertrees: Complexity and algorithms'. Together they form a unique fingerprint.

Cite this