Reconstruction of clonal trees and tumor composition from multi-sample sequencing data
Open Access
- 10 June 2015
- journal article
- research article
- Published by Oxford University Press (OUP) in Bioinformatics
- Vol. 31 (12), i62-i70
- https://doi.org/10.1093/bioinformatics/btv261
Abstract
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. Availability and implementation: An implementation of AncesTree is available at: http://compbio.cs.brown.edu/software. Contact:braphael@brown.edu Supplementary information: Supplementary data are available at Bioinformatics online.Keywords
This publication has 25 references indexed in Scilit:
- Inferring clonal evolution of tumors from single nucleotide somatic mutationsBMC Bioinformatics, 2014
- TrAp: a tree approach for fingerprinting subclonal tumor compositionNucleic Acids Research, 2013
- THetA: inferring intra-tumor heterogeneity from high-throughput DNA sequencing dataGenome Biology, 2013
- Monitoring chronic lymphocytic leukemia progression by whole genome sequencing reveals heterogeneous clonal evolution patternsBlood, 2012
- The Life History of 21 Breast CancersCell, 2012
- The clonal and mutational evolution spectrum of primary triple-negative breast cancersNature, 2012
- Intratumor Heterogeneity and Branched Evolution Revealed by Multiregion SequencingThe New England Journal of Medicine, 2012
- Clonal evolution in relapsed acute myeloid leukaemia revealed by whole-genome sequencingNature, 2012
- Efficient algorithms for inferring evolutionary treesNetworks, 1991
- The Clonal Evolution of Tumor Cell PopulationsScience, 1976