{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T07:34:23Z","timestamp":1769844863940,"version":"3.49.0"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,3,14]],"date-time":"2022-03-14T00:00:00Z","timestamp":1647216000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,3,14]],"date-time":"2022-03-14T00:00:00Z","timestamp":1647216000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec>\n                <jats:title>Background<\/jats:title>\n                <jats:p>Every tumor is composed of heterogeneous clones, each corresponding to a distinct subpopulation of cells that accumulated different types of somatic mutations, ranging from single-nucleotide variants (SNVs) to copy-number aberrations (CNAs). As the analysis of this intra-tumor heterogeneity has important clinical applications, several computational methods have been introduced to identify clones from DNA sequencing data. However, due to technological and methodological limitations, current analyses are restricted to identifying tumor clones only based on either SNVs or CNAs, preventing a comprehensive characterization of a tumor\u2019s clonal composition.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Results<\/jats:title>\n                <jats:p>To overcome these challenges, we formulate the identification of clones in terms of both SNVs and CNAs as a integration problem while accounting for uncertainty in the input SNV and CNA proportions. We thus characterize the computational complexity of this problem and we introduce PACTION (PArsimonious Clone Tree integratION), an algorithm that solves the problem using a mixed integer linear programming formulation. On simulated data, we show that tumor clones can be identified reliably, especially when further taking into account the ancestral relationships that can be inferred from the input SNVs and CNAs. On 49 tumor samples from 10 prostate cancer patients, our integration approach provides a higher resolution view of tumor evolution than previous studies.<\/jats:p>\n              <\/jats:sec><jats:sec>\n                <jats:title>Conclusion<\/jats:title>\n                <jats:p>PACTION is an accurate and fast method that reconstructs clonal architecture of cancer tumors by integrating SNV and CNA clones inferred using existing methods.<\/jats:p>\n              <\/jats:sec>","DOI":"10.1186\/s13015-022-00209-9","type":"journal-article","created":{"date-parts":[[2022,3,14]],"date-time":"2022-03-14T04:12:31Z","timestamp":1647231151000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Parsimonious Clone Tree Integration in cancer"],"prefix":"10.1186","volume":"17","author":[{"given":"Palash","family":"Sashittal","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Simone","family":"Zaccaria","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohammed","family":"El-Kebir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,3,14]]},"reference":[{"issue":"4260","key":"209_CR1","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1126\/science.959840","volume":"194","author":"PC Nowell","year":"1976","unstructured":"Nowell PC. The clonal evolution of tumor cell populations. Science. 1976;194(4260):23\u20138.","journal-title":"Science"},{"issue":"7467","key":"209_CR2","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1038\/nature12625","volume":"501","author":"RA Burrell","year":"2013","unstructured":"Burrell RA, McGranahan N, Bartek J, Swanton C. The causes and consequences of genetic heterogeneity in cancer evolution. Nature. 2013;501(7467):338\u201345.","journal-title":"Nature"},{"issue":"1","key":"209_CR3","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.ccell.2014.12.001","volume":"27","author":"N McGranahan","year":"2015","unstructured":"McGranahan N, Swanton C. Biological and therapeutic impact of intratumor heterogeneity in cancer evolution. Cancer Cell. 2015;27(1):15\u201326.","journal-title":"Cancer Cell"},{"issue":"10","key":"209_CR4","doi-asserted-by":"publisher","first-page":"1127","DOI":"10.1038\/ng.2762","volume":"45","author":"G Ciriello","year":"2013","unstructured":"Ciriello G, Miller ML, Aksoy BA, Senbabaoglu Y, Schultz N, Sander C. Emerging landscape of oncogenic signatures across human cancers. Nat Genet. 2013;45(10):1127\u201333.","journal-title":"Nat Genet"},{"issue":"7793","key":"209_CR5","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1038\/s41586-020-1969-6","volume":"578","author":"ICGC\/TCGA Pan-Cancer Analysis of Whole Genomes Consortium","year":"2020","unstructured":"ICGC\/TCGA Pan-Cancer Analysis of Whole Genomes Consortium, et al. Pan-cancer analysis of whole genomes. Nature. 2020;578(7793):82.","journal-title":"Nature"},{"issue":"7832","key":"209_CR6","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1038\/s41586-020-2698-6","volume":"587","author":"TB Watkins","year":"2020","unstructured":"Watkins TB, Lim EL, Petkovic M, Elizalde S, Birkbak NJ, Wilson GA, Moore DA, Gr\u00f6nroos E, Rowan A, Dewhurst SM, et al. Pervasive chromosomal instability and karyotype order in tumour evolution. Nature. 2020;587(7832):126\u201332.","journal-title":"Nature"},{"issue":"2","key":"209_CR7","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1038\/s41592-020-01013-2","volume":"18","author":"M Tarabichi","year":"2021","unstructured":"Tarabichi M, Salcedo A, Deshwar AG, Leathlobhair MN, Wintersinger J, Wedge DC, Van Loo P, Morris QD, Boutros PC. A practical guide to cancer subclonal reconstruction from dna sequencing. Nat Methods. 2021;18(2):144\u201355.","journal-title":"Nat Methods"},{"issue":"1","key":"209_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13059-015-0647-8","volume":"16","author":"V Popic","year":"2015","unstructured":"Popic V, Salari R, Hajirasouliha I, Kashef-Haghighi D, West RB, Batzoglou S. Fast and scalable inference of multi-sample cancer lineages. Genome Biol. 2015;16(1):1\u201317.","journal-title":"Genome Biol"},{"issue":"12","key":"209_CR9","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1093\/bioinformatics\/btv261","volume":"31","author":"M El-Kebir","year":"2015","unstructured":"El-Kebir M, Oesper L, Acheson-Field H, Raphael BJ. Reconstruction of clonal trees and tumor composition from multi-sample sequencing data. Bioinformatics. 2015;31(12):62\u201370.","journal-title":"Bioinformatics"},{"issue":"17","key":"209_CR10","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1093\/nar\/gkt641","volume":"41","author":"F Strino","year":"2013","unstructured":"Strino F, Parisi F, Micsinai M, Kluger Y. Trap: a tree approach for fingerprinting subclonal tumor composition. Nucleic Acids Res. 2013;41(17):165\u2013165.","journal-title":"Nucleic Acids Res"},{"issue":"14","key":"209_CR11","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1093\/bioinformatics\/btx270","volume":"33","author":"G Satas","year":"2017","unstructured":"Satas G, Raphael BJ. Tumor phylogeny inference using tree-constrained importance sampling. Bioinformatics. 2017;33(14):152\u201360.","journal-title":"Bioinformatics"},{"issue":"1","key":"209_CR12","doi-asserted-by":"publisher","first-page":"1008400","DOI":"10.1371\/journal.pcbi.1008400","volume":"17","author":"LK Sundermann","year":"2021","unstructured":"Sundermann LK, Wintersinger J, R\u00e4tsch G, Stoye J, Morris Q. Reconstructing tumor evolutionary histories and clone trees in polynomial-time with submarine. PLoS Comput Biol. 2021;17(1):1008400.","journal-title":"PLoS Comput Biol"},{"issue":"7","key":"209_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/gb-2013-14-7-r80","volume":"14","author":"L Oesper","year":"2013","unstructured":"Oesper L, Mahmoody A, Raphael BJ. Theta: inferring intra-tumor heterogeneity from high-throughput dna sequencing data. Genome Biol. 2013;14(7):1\u201321.","journal-title":"Genome Biol"},{"issue":"5","key":"209_CR14","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1016\/j.celrep.2014.04.055","volume":"7","author":"A Fischer","year":"2014","unstructured":"Fischer A, V\u00e1zquez-Garc\u00eda I, Illingworth CJ, Mustonen V. High-definition reconstruction of clonal composition in cancer. Cell Rep. 2014;7(5):1740\u201352.","journal-title":"Cell Rep"},{"issue":"1","key":"209_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/s41467-020-17967-y","volume":"11","author":"S Zaccaria","year":"2020","unstructured":"Zaccaria S, Raphael BJ. Accurate quantification of copy-number aberrations and whole-genome duplications in multi-sample tumor sequencing data. Nat Commun. 2020;11(1):1\u201313.","journal-title":"Nat Commun"},{"issue":"7625","key":"209_CR16","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1038\/nature19823","volume":"538","author":"F Notta","year":"2016","unstructured":"Notta F, Chan-Seng-Yue M, Lemire M, Li Y, Wilson GW, Connor AA, Denroche RE, Liang S-B, Brown AM, Kim JC, et al. A renewed model of pancreatic cancer evolution based on genomic rearrangement patterns. Nature. 2016;538(7625):378\u201382.","journal-title":"Nature"},{"key":"209_CR17","doi-asserted-by":"crossref","unstructured":"Zaccaria S, El-Kebir M, Klau GW, Raphael BJ. The copy-number tree mixture deconvolution problem and applications to multi-sample bulk sequencing tumor data. In: International Conference on Research in Computational Molecular Biology, 2017:318\u2013335. Springer","DOI":"10.1007\/978-3-319-56970-3_20"},{"issue":"1","key":"209_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13059-016-1139-1","volume":"18","author":"AW McPherson","year":"2017","unstructured":"McPherson AW, Roth A, Ha G, Chauve C, Steif A, de Souza CP, Eirew P, Bouchard-C\u00f4t\u00e9 A, Aparicio S, Sahinalp SC, et al. Remixt: clone-specific genomic structure estimation in cancer. Genome Biol. 2017;18(1):1\u201314.","journal-title":"Genome Biol"},{"issue":"7","key":"209_CR19","doi-asserted-by":"publisher","first-page":"689","DOI":"10.1089\/cmb.2017.0253","volume":"25","author":"S Zaccaria","year":"2018","unstructured":"Zaccaria S, El-Kebir M, Klau GW, Raphael BJ. Phylogenetic copy-number factorization of multiple tumor samples. J Comput Biol. 2018;25(7):689\u2013708.","journal-title":"J Comput Biol"},{"issue":"1","key":"209_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13059-015-0602-8","volume":"16","author":"AG Deshwar","year":"2015","unstructured":"Deshwar AG, Vembu S, Yung CK, Jang GH, Stein L, Morris Q. Phylowgs: reconstructing subclonal composition and evolution from whole-genome sequencing of tumors. Genome Biol. 2015;16(1):1\u201320.","journal-title":"Genome Biol"},{"issue":"1","key":"209_CR21","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/j.cels.2016.07.004","volume":"3","author":"M El-Kebir","year":"2016","unstructured":"El-Kebir M, Satas G, Oesper L, Raphael BJ. Inferring the mutational history of a tumor using multi-state perfect phylogeny mixtures. Cell Syst. 2016;3(1):43\u201353. https:\/\/doi.org\/10.1016\/j.cels.2016.07.004.","journal-title":"Cell Syst."},{"issue":"37","key":"209_CR22","first-page":"5528","volume":"113","author":"Y Jiang","year":"2016","unstructured":"Jiang Y, Qiu Y, Minn AJ, Zhang NR. Assessing intratumor heterogeneity and tracking longitudinal and spatial clonal evolutionary history by next-generation sequencing. Proc Natl Acad Sci. 2016;113(37):5528\u201337.","journal-title":"Proc Natl Acad Sci"},{"issue":"7547","key":"209_CR23","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1038\/nature14347","volume":"520","author":"G Gundem","year":"2015","unstructured":"Gundem G, Van Loo P, Kremeyer B, Alexandrov LB, Tubio JM, Papaemmanuil E, Brewer DS, Kallio HM, H\u00f6gn\u00e4s G, Annala M, et al. The evolutionary history of lethal metastatic prostate cancer. Nature. 2015;520(7547):353\u20137.","journal-title":"Nature"},{"issue":"22","key":"209_CR24","doi-asserted-by":"publisher","first-page":"2109","DOI":"10.1056\/NEJMoa1616288","volume":"376","author":"M Jamal-Hanjani","year":"2017","unstructured":"Jamal-Hanjani M, Wilson GA, McGranahan N, Birkbak NJ, Watkins TB, Veeriah S, Shafi S, Johnson DH, Mitter R, Rosenthal R, et al. Tracking the evolution of non-small-cell lung cancer. N Engl J Med. 2017;376(22):2109\u201321.","journal-title":"N Engl J Med"},{"issue":"3","key":"209_CR25","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1038\/nrg.2015.16","volume":"17","author":"C Gawad","year":"2016","unstructured":"Gawad C, Koh W, Quake SR. Single-cell genome sequencing: current state of the science. Nat Rev Genet. 2016;17(3):175.","journal-title":"Nat Rev Genet"},{"issue":"8","key":"209_CR26","doi-asserted-by":"publisher","first-page":"1287","DOI":"10.1101\/gr.209973.116","volume":"27","author":"ML Leung","year":"2017","unstructured":"Leung ML, Davis A, Gao R, Casasent A, Wang Y, Sei E, Vilar E, Maru D, Kopetz S, Navin NE. Single-cell dna sequencing reveals a late-dissemination model in metastatic colorectal cancer. Genome Res. 2017;27(8):1287\u201399.","journal-title":"Genome Res"},{"issue":"9","key":"209_CR27","doi-asserted-by":"publisher","first-page":"1349","DOI":"10.1093\/bioinformatics\/btv003","volume":"31","author":"S Malikic","year":"2015","unstructured":"Malikic S, McPherson AW, Donmez N, Sahinalp CS. Clonality inference in multiple tumor samples using phylogeny. Bioinformatics. 2015;31(9):1349\u201356.","journal-title":"Bioinformatics"},{"issue":"4","key":"209_CR28","doi-asserted-by":"publisher","first-page":"1003535","DOI":"10.1371\/journal.pcbi.1003535","volume":"10","author":"RF Schwarz","year":"2014","unstructured":"Schwarz RF, Trinh A, Sipos B, Brenton JD, Goldman N, Markowetz F. Phylogenetic quantification of intra-tumour heterogeneity. PLoS Comput Biol. 2014;10(4):1003535.","journal-title":"PLoS Comput Biol"},{"key":"209_CR29","doi-asserted-by":"crossref","unstructured":"El-Kebir M, Raphael BJ, Shamir R, Sharan R, Zaccaria S, Zehavi M, Zeira R. Copy-number evolution problems: complexity and algorithms. In: International Workshop on Algorithms in Bioinformatics, 2016;137\u2013149. Springer","DOI":"10.1007\/978-3-319-43681-4_11"},{"issue":"1","key":"209_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13015-017-0103-2","volume":"12","author":"M El-Kebir","year":"2017","unstructured":"El-Kebir M, Raphael BJ, Shamir R, Sharan R, Zaccaria S, Zehavi M, Zeira R. Complexity and algorithms for copy-number evolution problems. Algorithms Mol Biol. 2017;12(1):1\u201311.","journal-title":"Algorithms Mol Biol"},{"issue":"1","key":"209_CR31","first-page":"118","volume":"6","author":"T Wu","year":"2008","unstructured":"Wu T, Moulton V, Steel M. Refining phylogenetic trees given additional data: an algorithm based on parsimony. IEEE\/ACM Trans Comput Biol Bioinform. 2008;6(1):118\u201325.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform"},{"issue":"3","key":"209_CR32","first-page":"252","volume":"41","author":"RK Ahuja","year":"1995","unstructured":"Ahuja RK, Magnanti TL, Orlin JB, Weihe K. Network flows: theory, algorithms and applications. ZOR Methods Models Operat Res. 1995;41(3):252\u20134.","journal-title":"ZOR Methods Models Operat Res"},{"key":"209_CR33","unstructured":"Garey MR, Johnson DS. Computers and intractability. JSTOR: A guide to the theory of NP-completeness; 1983."},{"issue":"4","key":"209_CR34","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1137\/0204035","volume":"4","author":"MR Garey","year":"1975","unstructured":"Garey MR, Johnson DS. Complexity results for multiprocessor scheduling under resource constraints. SIAM J Comput. 1975;4(4):397\u2013411.","journal-title":"SIAM J Comput"},{"key":"209_CR35","volume-title":"Steiner trees in industries","author":"D Fern\u00e1ndez-Baca","year":"2000","unstructured":"Fern\u00e1ndez-Baca D. The perfect phylogeny problem. In: Zu DZ, Cheng X, editors. Steiner trees in industries. Amsterdam: Kluwer Acedemic Publishers; 2000."},{"issue":"6","key":"209_CR36","doi-asserted-by":"publisher","first-page":"066123","DOI":"10.1103\/PhysRevE.63.066123","volume":"63","author":"PL Krapivsky","year":"2001","unstructured":"Krapivsky PL, Redner S. Organization of growing random networks. Phys Rev E. 2001;63(6):066123.","journal-title":"Phys Rev E"},{"key":"209_CR37","doi-asserted-by":"crossref","unstructured":"Govek K, Sikes C, Oesper L. A consensus approach to infer tumor evolutionary histories. In: Proceedings of the 2018 Acm International Conference on Bioinformatics, Computational Biology, and Health Informatics, 2018;63\u201372","DOI":"10.1145\/3233547.3233584"},{"issue":"5","key":"209_CR38","first-page":"056002","volume":"18","author":"H Teimouri","year":"2021","unstructured":"Teimouri H, Kolomeisky AB. Temporal order of mutations influences cancer initiation dynamics. bioRxiv. 2021;18(5):056002.","journal-title":"bioRxiv"},{"issue":"7","key":"209_CR39","doi-asserted-by":"publisher","first-page":"1135","DOI":"10.1158\/1940-6207.CAPR-10-0374","volume":"4","author":"K Sprouffske","year":"2011","unstructured":"Sprouffske K, Pepper JW, Maley CC. Accurate reconstruction of the temporal order of mutations in neoplastic progression. Cancer Prev Res. 2011;4(7):1135\u201344.","journal-title":"Cancer Prev Res"},{"issue":"2","key":"209_CR40","doi-asserted-by":"publisher","first-page":"89244","DOI":"10.1371\/journal.pone.0089244","volume":"9","author":"J Guo","year":"2014","unstructured":"Guo J, Guo H, Wang Z. Inferring the temporal order of cancer gene mutations in individual tumor samples. PLoS ONE. 2014;9(2):89244.","journal-title":"PLoS ONE"},{"issue":"11","key":"209_CR41","doi-asserted-by":"publisher","first-page":"1007451","DOI":"10.1371\/journal.pcbi.1007451","volume":"15","author":"S Khakabimamaghani","year":"2019","unstructured":"Khakabimamaghani S, Ding D, Snow O, Ester M. Uncovering the subtype-specific temporal order of cancer pathway dysregulation. PLoS Comput Biol. 2019;15(11):1007451.","journal-title":"PLoS Comput Biol"},{"key":"209_CR42","first-page":"16","volume":"35","author":"J Barnett","year":"2010","unstructured":"Barnett J, Correia H, Johnson P, Laughlin M, Wilson K. Darwin meets graph theory on a strange planet: counting full n-ary trees with labeled leafs. Alabama J Math. 2010;35:16\u201323.","journal-title":"Alabama J Math."},{"issue":"4","key":"209_CR43","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1016\/j.cels.2020.04.001","volume":"10","author":"G Satas","year":"2020","unstructured":"Satas G, Zaccaria S, Mon G, Raphael BJ. Scarlet: single-cell tumor phylogeny inference with copy-number constrained mutation losses. Cell Syst. 2020;10(4):323\u201332.","journal-title":"Cell Syst"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-022-00209-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-022-00209-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-022-00209-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,14]],"date-time":"2022-03-14T04:12:41Z","timestamp":1647231161000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/s13015-022-00209-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,14]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["209"],"URL":"https:\/\/doi.org\/10.1186\/s13015-022-00209-9","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,14]]},"assertion":[{"value":"15 November 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 January 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 March 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"3"}}