title: Reconstruction of clonal trees and tumor composition from multi-sample sequencing data.
abstract: BACKGROUND
  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.
  
  
  METHODS
  An implementation of AncesTree is available at: http://compbio.cs.brown.edu/software.
authors.affiliation: Center for Computational Molecular Biology and Department of Computer Science, Brown University, Providence, RI 02912, USA.
authors.forename: Mohammed
authors.initials: M
authors.lastname: El-Kebir
authors.affiliation: Center for Computational Molecular Biology and Department of Computer Science, Brown University, Providence, RI 02912, USA.
authors.forename: Layla
authors.initials: L
authors.lastname: Oesper
authors.affiliation: Center for Computational Molecular Biology and Department of Computer Science, Brown University, Providence, RI 02912, USA.
authors.forename: Hannah
authors.initials: H
authors.lastname: Acheson-Field
authors.affiliation: Center for Computational Molecular Biology and Department of Computer Science, Brown University, Providence, RI 02912, USA.
authors.forename: Benjamin J
authors.initials: BJ
authors.lastname: Raphael
mesh_terms: D000465:Algorithms; D060965:Clonal Evolution / Q000235:genetics*; D005787:Gene Frequency; D059014:High-Throughput Nucleotide Sequencing / Q000379:methods*; D006801:Humans; D015233:Models, Statistical; D009154:Mutation / Q000235:genetics*; D009369:Neoplasms / Q000145:classification* / Q000235:genetics*; D017422:Sequence Analysis, DNA / Q000379:methods*