Consensus Tree Under the Ancestor–Descendant Distance is NP-Hard

Yuanyuan Qi, Mohammed El-Kebir

Research output: Contribution to journalArticlepeer-review


Due to uncertainty in tumor phylogeny inference from sequencing data, many methods infer multiple, equally plausible phylogenies for the same cancer. To summarize the solution space T of tumor phylogenies, consensus tree methods seek a single best representative tree S under a specified pairwise tree distance function. One such distance function is the ancestor–descendant (AD) distance d(T‚ T0), which equals the size of the symmetric difference of the transitive closures of the edge sets E(T) and E(T0). Here, we show that finding a consensus tree S for tumor phylogenies T that minimizes the total AD distance +T∈T d(S‚ T) is NP-hard.

Original languageEnglish (US)
Pages (from-to)58-70
Number of pages13
JournalJournal of Computational Biology
Issue number1
StatePublished - Jan 1 2024


  • cancer
  • consensus tree
  • infinite sites assumption
  • intra-tumor heterogeneity

ASJC Scopus subject areas

  • Modeling and Simulation
  • Molecular Biology
  • Genetics
  • Computational Mathematics
  • Computational Theory and Mathematics


Dive into the research topics of 'Consensus Tree Under the Ancestor–Descendant Distance is NP-Hard'. Together they form a unique fingerprint.

Cite this