{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T08:50:48Z","timestamp":1772614248905,"version":"3.50.1"},"reference-count":26,"publisher":"Oxford University Press (OUP)","issue":"12","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":480,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015,6,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>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.<\/jats:p>\n               <jats:p>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.<\/jats:p>\n               <jats:p>Availability and implementation: An implementation of AncesTree is available at: http:\/\/compbio.cs.brown.edu\/software.<\/jats:p>\n               <jats:p>Contact: \u00a0braphael@brown.edu<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btv261","type":"journal-article","created":{"date-parts":[[2015,6,13]],"date-time":"2015-06-13T17:12:36Z","timestamp":1434215556000},"page":"i62-i70","source":"Crossref","is-referenced-by-count":184,"title":["Reconstruction of clonal trees and tumor composition from multi-sample sequencing data"],"prefix":"10.1093","volume":"31","author":[{"given":"Mohammed","family":"El-Kebir","sequence":"first","affiliation":[{"name":"Center for Computational Molecular Biology and Department of Computer Science, Brown University, Providence, RI 02912, USA"}]},{"given":"Layla","family":"Oesper","sequence":"additional","affiliation":[{"name":"Center for Computational Molecular Biology and Department of Computer Science, Brown University, Providence, RI 02912, USA"}]},{"given":"Hannah","family":"Acheson-Field","sequence":"additional","affiliation":[{"name":"Center for Computational Molecular Biology and Department of Computer Science, Brown University, Providence, RI 02912, USA"}]},{"given":"Benjamin J.","family":"Raphael","sequence":"additional","affiliation":[{"name":"Center for Computational Molecular Biology and Department of Computer Science, Brown University, Providence, RI 02912, USA"}]}],"member":"286","published-online":{"date-parts":[[2015,6,10]]},"reference":[{"key":"2023020115205684100_btv261-B1","article-title":"Exact calculation of beta inequalities","volume-title":"Technical report","author":"Cook","year":"2005"},{"key":"2023020115205684100_btv261-B2","doi-asserted-by":"crossref","first-page":"506","DOI":"10.1038\/nature10738","article-title":"Clonal evolution in relapsed acute myeloid leukaemia revealed by whole-genome sequencing","volume":"481","author":"Ding","year":"2012","journal-title":"Nature"},{"key":"2023020115205684100_btv261-B3","doi-asserted-by":"crossref","first-page":"883","DOI":"10.1056\/NEJMoa1113205","article-title":"Intratumor heterogeneity and branched evolution revealed by multiregion sequencing","volume":"366","author":"Gerlinger","year":"2012","journal-title":"N. Engl. J. Med."},{"key":"2023020115205684100_btv261-B4","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1038\/ng.2891","article-title":"Genomic architecture and evolution of clear cell renal cell carcinomas defined by multiregion sequencing","volume":"46","author":"Gerlinger","year":"2014","journal-title":"Nat. Genet."},{"key":"2023020115205684100_btv261-B5","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1002\/net.3230210104","article-title":"Efficient algorithms for inferring evolutionary trees","volume":"21","author":"Gusfield","year":"1991","journal-title":"Networks"},{"key":"2023020115205684100_btv261-B6","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences\u2014Computer Science and Computational Biology","author":"Gusfield","year":"1997"},{"key":"2023020115205684100_btv261-B7","first-page":"354","article-title":"Reconstructing mutational history in multiply sampled tumors using perfect phylogeny mixtures","volume-title":"Algorithms in Bioinformatics\u201414th International Workshop, WABI 2014","author":"Hajirasouliha","year":"2014"},{"key":"2023020115205684100_btv261-B8","doi-asserted-by":"crossref","first-page":"i78","DOI":"10.1093\/bioinformatics\/btu284","article-title":"A combinatorial approach for analyzing intra-tumor heterogeneity from high-throughput sequencing data","volume":"30","author":"Hajirasouliha","year":"2014","journal-title":"Bioinformatics"},{"key":"2023020115205684100_btv261-B9","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1186\/1471-2105-15-35","article-title":"Inferring clonal evolution of tumors from single nucleotide somatic mutations","volume":"15","author":"Jiao","year":"2014","journal-title":"BMC Bioinformatics"},{"key":"2023020115205684100_btv261-B10","doi-asserted-by":"crossref","first-page":"1349","DOI":"10.1093\/bioinformatics\/btv003","article-title":"Clonality inference in multiple tumor samples using phylogeny","volume":"31","author":"Malikic","year":"2015","journal-title":"Bioinformatics"},{"key":"2023020115205684100_btv261-B11","doi-asserted-by":"crossref","first-page":"e1003665","DOI":"10.1371\/journal.pcbi.1003665","article-title":"Sciclone: inferring clonal architecture and tracking the spatial and temporal patterns of tumor evolution","volume":"10","author":"Miller","year":"2014","journal-title":"PLoS Comput. Biol."},{"key":"2023020115205684100_btv261-B12","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1186\/s13059-014-0452-9","article-title":"Cancer genomics: one cell at a time","volume":"15","author":"Navin","year":"2014","journal-title":"Genome Biol."},{"key":"2023020115205684100_btv261-B13","doi-asserted-by":"crossref","first-page":"1097","DOI":"10.1101\/gr.151670.112","article-title":"Genome evolution during progression to breast cancer","volume":"23","author":"Newburger","year":"2013","journal-title":"Genome Res."},{"key":"2023020115205684100_btv261-B14","doi-asserted-by":"crossref","first-page":"994","DOI":"10.1016\/j.cell.2012.04.023","article-title":"The life history of 21 breast cancers","volume":"149","author":"Nik-Zainal","year":"2012","journal-title":"Cell"},{"key":"2023020115205684100_btv261-B15","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1126\/science.959840","article-title":"The clonal evolution of tumor cell populations","volume":"194","author":"Nowell","year":"1976","journal-title":"Science"},{"key":"2023020115205684100_btv261-B16","doi-asserted-by":"crossref","first-page":"R80","DOI":"10.1186\/gb-2013-14-7-r80","article-title":"Theta: inferring intra-tumor heterogeneity from high-throughput DNA sequencing data","volume":"14","author":"Oesper","year":"2013","journal-title":"Genome Biol."},{"key":"2023020115205684100_btv261-B17","doi-asserted-by":"crossref","first-page":"3532","DOI":"10.1093\/bioinformatics\/btu651","article-title":"Quantifying tumor heterogeneity in whole-genome and whole-exome sequencing data","volume":"30","author":"Oesper","year":"2014","journal-title":"Bioinformatics"},{"key":"2023020115205684100_btv261-B18","article-title":"Fast and scalable inference of multi-sample cancer lineages","author":"Popic","year":"2014"},{"key":"2023020115205684100_btv261-B19","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1038\/nmeth.2883","article-title":"Pyclone: statistical inference of clonal population structure in cancer","volume":"11","author":"Roth","year":"2014","journal-title":"Nat. Methods"},{"key":"2023020115205684100_btv261-B20","doi-asserted-by":"crossref","first-page":"4191","DOI":"10.1182\/blood-2012-05-433540","article-title":"Monitoring chronic lymphocytic leukemia progression by whole genome sequencing reveals heterogeneous clonal evolution patterns","volume":"120","author":"Schuh","year":"2012","journal-title":"Blood"},{"key":"2023020115205684100_btv261-B21","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1038\/nature10933","article-title":"The clonal and mutational evolution spectrum of primary triple-negative breast cancers","volume":"486","author":"Shah","year":"2012","journal-title":"Nature"},{"key":"2023020115205684100_btv261-B22","doi-asserted-by":"crossref","first-page":"e165","DOI":"10.1093\/nar\/gkt641","article-title":"Trap: a tree approach for fingerprinting subclonal tumor composition","volume":"41","author":"Strino","year":"2013","journal-title":"Nucleic Acids Res."},{"key":"2023020115205684100_btv261-B23","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1038\/nature13600","article-title":"Clonal evolution in breast cancer revealed by single nucleus genome sequencing","volume":"512","author":"Wang","year":"2014","journal-title":"Nature"},{"key":"2023020115205684100_btv261-B24","volume-title":"Integer Programming","author":"Wolsey","year":"1998"},{"key":"2023020115205684100_btv261-B25","doi-asserted-by":"crossref","first-page":"e1003703","DOI":"10.1371\/journal.pcbi.1003703","article-title":"Inferring clonal composition from multiple sections of a breast cancer","volume":"10","author":"Zare","year":"2014","journal-title":"PLoS Comput. Biol."},{"key":"2023020115205684100_btv261-B26","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1126\/science.1256930","article-title":"Intratumor heterogeneity in localized lung adenocarcinomas delineated by multiregion sequencing","volume":"346","author":"Zhang","year":"2014","journal-title":"Science"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/31\/12\/i62\/49014148\/bioinformatics_31_12_i62.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/31\/12\/i62\/49014148\/bioinformatics_31_12_i62.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,2]],"date-time":"2023-02-02T00:04:05Z","timestamp":1675296245000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/31\/12\/i62\/216528"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,10]]},"references-count":26,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2015,6,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btv261","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2015,6,15]]},"published":{"date-parts":[[2015,6,10]]}}}