Parsimonious clone tree reconciliation in cancer

Palash Sashittal, Simone Zaccaria, Mohammed El-Kebir

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


Every tumor is composed of heterogeneous clones, each corresponding to a distinct subpopulation of cells that accumulated different types of somatic mutations, ranging from single-nucleotide variants (SNVs) to copy-number aberrations (CNAs). As the analysis of this intra-tumor heterogeneity has important clinical applications, several computational methods have been introduced to identify clones from DNA sequencing data. However, due to technological and methodological limitations, current analyses are restricted to identifying tumor clones only based on either SNVs or CNAs, preventing a comprehensive characterization of a tumor's clonal composition. To overcome these challenges, we formulate the identification of clones in terms of both SNVs and CNAs as a reconciliation problem while accounting for uncertainty in the input SNV and CNA proportions. We thus characterize the computational complexity of this problem and we introduce a mixed integer linear programming formulation to solve it exactly. On simulated data, we show that tumor clones can be identified reliably, especially when further taking into account the ancestral relationships that can be inferred from the input SNVs and CNAs. On 49 tumor samples from 10 prostate cancer patients, our reconciliation approach provides a higher resolution view of tumor evolution than previous studies.

Original languageEnglish (US)
Title of host publication21st International Workshop on Algorithms in Bioinformatics, WABI 2021
EditorsAlessandra Carbone, Mohammed El-Kebir
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772006
StatePublished - Jul 1 2021
Event21st International Workshop on Algorithms in Bioinformatics, WABI 2021 - Virtual, Chicago, United States
Duration: Aug 2 2021Aug 4 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference21st International Workshop on Algorithms in Bioinformatics, WABI 2021
Country/TerritoryUnited States
CityVirtual, Chicago


  • Intra-tumor heterogeneity
  • Mixed integer linear programming
  • Phylogenetics

ASJC Scopus subject areas

  • Software


Dive into the research topics of 'Parsimonious clone tree reconciliation in cancer'. Together they form a unique fingerprint.

Cite this