Reconstruction of clonal trees and tumor composition from multi-sample sequencing data

Mohammed El-Kebir, Layla Oesper, Hannah Acheson-Field, Benjamin J. Raphael

Research output: Contribution to journalArticlepeer-review

125 Scopus citations


Motivation: DNA sequencing of multiple samples from the same tumor provides data to analyze the process of clonal evolution in the population of cells that give rise to a tumor. Results: We formalize the problem of reconstructing the clonal evolution of a tumor using single-nucleotide mutations as the variant allele frequency (VAF) factorization problem. We derive a combinatorial characterization of the solutions to this problem and show that the problem is NP-complete. We derive an integer linear programming solution to the VAF factorization problem in the case of error-free data and extend this solution to real data with a probabilistic model for errors. The resulting AncesTree algorithm is better able to identify ancestral relationships between individual mutations than existing approaches, particularly in ultra-deep sequencing data when high read counts for mutations yield high confidence VAFs.

Original languageEnglish (US)
Pages (from-to)i62-i70
Issue number12
StatePublished - Jun 15 2015
Externally publishedYes

All Science Journal Classification (ASJC) codes

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


Dive into the research topics of 'Reconstruction of clonal trees and tumor composition from multi-sample sequencing data'. Together they form a unique fingerprint.

Cite this