Detecting evolutionary patterns of cancers using consensus trees

Sarah Christensen, Juho Kim, Nicholas Chia, Oluwasanmi Koyejo, Mohammed El-Kebir

Research output: Contribution to journalArticlepeer-review


Motivation: While each cancer is the result of an isolated evolutionary process, there are repeated patterns in tumorigenesis defined by recurrent driver mutations and their temporal ordering. Such repeated evolutionary trajectories hold the potential to improve stratification of cancer patients into subtypes with distinct survival and therapy response profiles. However, current cancer phylogeny methods infer large solution spaces of plausible evolutionary histories from the same sequencing data, obfuscating repeated evolutionary patterns. Results: To simultaneously resolve ambiguities in sequencing data and identify cancer subtypes, we propose to leverage common patterns of evolution found in patient cohorts. We first formulate the Multiple Choice Consensus Tree problem, which seeks to select a tumor tree for each patient and assign patients into clusters in such a way that maximizes consistency within each cluster of patient trees. We prove that this problem is NP-hard and develop a heuristic algorithm, Revealing Evolutionary Consensus Across Patients (RECAP), to solve this problem in practice. Finally, on simulated data, we show RECAP outperforms existing methods that do not account for patient subtypes. We then use RECAP to resolve ambiguities in patient trees and find repeated evolutionary trajectories in lung and breast cancer cohorts.

Original languageEnglish (US)
Pages (from-to)i684-i691
JournalBioinformatics (Oxford, England)
Issue numberSupplement_2
StatePublished - Dec 1 2020

ASJC Scopus subject areas

  • Computational Mathematics
  • Molecular Biology
  • Biochemistry
  • Statistics and Probability
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'Detecting evolutionary patterns of cancers using consensus trees'. Together they form a unique fingerprint.

Cite this