Reconstruction of clonal trees and tumor composition from multi-sample sequencing data.
Bottom Line: 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.
Affiliation: Center for Computational Molecular Biology and Department of Computer Science, Brown University, Providence, RI 02912, USA.Show MeSH
Related in: MedlinePlus
Mentions: Cancer is a disease resulting from somatic mutations that accumulate during an individual’s lifetime and lead to uncontrolled growth of a collection of cells into a tumor. The clonal theory of cancer (Nowell, 1976) predicts that all cells within a tumor have descended from a single founder cell and that subsequent clonal expansions occur from additional advantageous mutations. As a result, the cells within a tumor may differ in their complement of somatic mutations, with each cell being a descendant of a clone from a clonal expansion (Fig. 1A). High-coverage sequencing of tumor genomes allows one to study this intra-tumor heterogeneity by measuring the frequencies of mutations within a tumor (Ding et al., 2012; Nik-Zainal et al., 2012; Shah et al., 2012). Characterization of intra-tumor heterogeneity and inference of the clonal evolutionary history of somatic mutations within a tumor provide useful insight in the tumor’s development and may help inform treatment.Fig. 1.
Affiliation: Center for Computational Molecular Biology and Department of Computer Science, Brown University, Providence, RI 02912, USA.