{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T10:58:03Z","timestamp":1774522683078,"version":"3.50.1"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,2,18]],"date-time":"2026-02-18T00:00:00Z","timestamp":1771372800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T00:00:00Z","timestamp":1774483200000},"content-version":"vor","delay-in-days":36,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-2046488"],"award-info":[{"award-number":["CCF-2046488"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Background<\/jats:title>\n                    <jats:p>Cancer phylogenies are key to understanding tumor evolution. However, due to the uncertainty in phylogenetic estimation, one typically infers many, equally-plausible phylogenies from bulk DNA sequencing data of tumors, hindering downstream analysis that relies on correct phylogenies.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>\n                      To resolve this challenge, we introduce Sapling, a method to solve two variants of the\n                      <jats:sc>Backbone Tree Inference from Reads<\/jats:sc>\n                      problem, which seeks a small set of backbone trees on a subset of mutations that collectively summarize the space of plausible cancer phylogenies. We prove that the problems are NP-hard.\n                    <\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Conclusions<\/jats:title>\n                    <jats:p>On simulated and real data, we demonstrate that Sapling is capable of inferring high-quality backbone trees that adequately summarize the space of plausible cancer phylogenies. In addition, we demonstrate that Sapling is able to infer full-size trees with higher likelihoods than state-of-the-art methods.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1186\/s13015-025-00295-5","type":"journal-article","created":{"date-parts":[[2026,2,18]],"date-time":"2026-02-18T19:24:50Z","timestamp":1771442690000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Inferring and summarizing tumor phylogenies from bulk DNA data"],"prefix":"10.1186","volume":"21","author":[{"given":"Yuanyuan","family":"Qi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Henri","family":"Schmidt","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":[[2026,2,18]]},"reference":[{"key":"295_CR1","doi-asserted-by":"crossref","unstructured":"Nowell PC. The clonal evolution of tumor cell populations. Science. 1976;194(4260):23\u20138.","DOI":"10.1126\/science.959840"},{"key":"295_CR2","doi-asserted-by":"publisher","unstructured":"Lohr JG, Stojanov P, Carter SL, Cruz-Gordillo P, Lawrence MS, Auclair D, et al. Widespread genetic heterogeneity in multiple myeloma: implications for targeted therapy. Cancer Cell. 2014;25(1):91\u2013101. https:\/\/doi.org\/10.1016\/j.ccr.2013.12.015.","DOI":"10.1016\/j.ccr.2013.12.015"},{"key":"295_CR3","doi-asserted-by":"publisher","unstructured":"Schwartz S. The evolution of tumour phylogenetics: principles and practice. Nat Rev Genet. 2017;18(4):213\u201329. https:\/\/doi.org\/10.1038\/nrg.2016.170.","DOI":"10.1038\/nrg.2016.170"},{"key":"295_CR4","doi-asserted-by":"publisher","unstructured":"Alves JM, Prieto T, Posada D. Multiregional tumor trees are not phylogenies. Trends in Cancer. 2017;3(8):546\u201350. https:\/\/doi.org\/10.1016\/j.trecan.2017.06.004.","DOI":"10.1016\/j.trecan.2017.06.004"},{"issue":"7681","key":"295_CR5","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1038\/nature24473","volume":"551","author":"M \u0141uksza","year":"2017","unstructured":"\u0141uksza M, Riaz N, Makarov V, Balachandran VP, Hellmann MD, Solovyov A, et al. A neoantigen fitness model predicts tumour response to checkpoint blockade immunotherapy. Nature. 2017;551(7681):517\u201320.","journal-title":"Nature"},{"key":"295_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/s41586-024-08507-5","volume":"639","author":"DA Braun","year":"2025","unstructured":"Braun DA, Moranzoni G, Chea V, McGregor BA, Blass E, Tu CR, et al. A neoantigen vaccine generates antitumour immunity in renal cell carcinoma. Nature. 2025;639:1\u20139.","journal-title":"Nature"},{"issue":"5","key":"295_CR7","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1038\/s41588-018-0106-z","volume":"50","author":"M El-Kebir","year":"2018","unstructured":"El-Kebir M, Satas G, Raphael BJ. Inferring parsimonious migration histories for metastatic cancers. Nat Genet. 2018;50(5):718\u201326.","journal-title":"Nat Genet"},{"issue":"9","key":"295_CR8","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1038\/s41592-018-0108-x","volume":"15","author":"G Caravagna","year":"2018","unstructured":"Caravagna G, Giarratano Y, Ramazzotti D, Tomlinson I, Graham TA, Sanguinetti G, et al. Detecting repeated cancer evolution from multi-region tumor sequencing data. Nat Methods. 2018;15(9):707\u201314.","journal-title":"Nat Methods"},{"issue":"7","key":"295_CR9","first-page":"1078","volume":"33","author":"E-K Ivanovic","year":"2023","unstructured":"Ivanovic E-K. Modeling and predicting cancer clonal evolution with reinforcement learning. Genome Res. 2023;33(7):1078\u201388.","journal-title":"Genome Res"},{"issue":"2 Supplement","key":"295_CR10","doi-asserted-by":"publisher","first-page":"684","DOI":"10.1093\/bioinformatics\/btaa801","volume":"36","author":"S Christensen","year":"2020","unstructured":"Christensen S, Kim J, Chia N, Koyejo O, El-Kebir M. Detecting evolutionary patterns of cancers using consensus trees. Bioinformatics. 2020;36(2 Supplement):684\u201391.","journal-title":"Bioinformatics"},{"key":"295_CR11","doi-asserted-by":"publisher","unstructured":"Qi Y, Pradhan D, El-Kebir M. Implications of non-uniqueness in phylogenetic deconvolution of bulk DNA samples of tumors. Algorithms Mol Biol. 2019;14(1):19. https:\/\/doi.org\/10.1186\/s13015-019-0155-6.","DOI":"10.1186\/s13015-019-0155-6"},{"issue":"12","key":"295_CR12","doi-asserted-by":"publisher","first-page":"1012653","DOI":"10.1371\/journal.pcbi.1012653","volume":"20","author":"E Kulman","year":"2024","unstructured":"Kulman E, Kuang R, Morris Q. Orchard: Building large cancer phylogenies using stochastic combinatorial search. PLoS Comput Biol. 2024;20(12):1012653. https:\/\/doi.org\/10.1371\/journal.pcbi.1012653.","journal-title":"PLoS Comput Biol"},{"issue":"4","key":"295_CR13","doi-asserted-by":"publisher","DOI":"10.1016\/j.xpro.2022.101706","volume":"3","author":"E Kulman","year":"2022","unstructured":"Kulman E, Wintersinger J, Morris Q. Reconstructing cancer phylogenies using pairtree, a clone tree reconstruction algorithm. STAR Protoc. 2022;3(4):101706.","journal-title":"STAR Protoc"},{"issue":"3","key":"295_CR14","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1158\/2643-3230.BCD-21-0092","volume":"3","author":"J Wintersinger","year":"2022","unstructured":"Wintersinger J. Reconstructing complex cancer evolutionary histories from multiple bulk DNA samples using pairtree. Blood Cancer Discov. 2022;3(3):208\u201319.","journal-title":"Blood Cancer Discov"},{"key":"295_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13059-015-0602-8","volume":"16","author":"AG Deshwar","year":"2015","unstructured":"Deshwar AG. PhyloWGS: reconstructing subclonal composition and evolution from whole-genome sequencing of tumors. Genome Biol. 2015;16:1\u201320.","journal-title":"Genome Biol"},{"issue":"12","key":"295_CR16","doi-asserted-by":"publisher","first-page":"1012631","DOI":"10.1371\/journal.pcbi.1012631","volume":"20","author":"H Schmidt","year":"2024","unstructured":"Schmidt H, Raphael BJ. A regression based approach to phylogenetic reconstruction from multi-sample bulk DNA sequencing of tumors. PLoS Comput Biol. 2024;20(12):1012631.","journal-title":"PLoS Comput Biol"},{"issue":"Supplement 1","key":"295_CR17","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1093\/bioinformatics\/btad230","volume":"39","author":"Z Guang","year":"2023","unstructured":"Guang Z, Smith-Erb M, Oesper L. A weighted distance-based approach for deriving consensus tumor evolutionary trees. Bioinformatics. 2023;39(Supplement 1):204\u201312. https:\/\/doi.org\/10.1093\/bioinformatics\/btad230.","journal-title":"Bioinformatics"},{"issue":"7","key":"295_CR18","doi-asserted-by":"publisher","first-page":"2090","DOI":"10.1093\/bioinformatics\/btz869","volume":"36","author":"Z DiNardo","year":"2020","unstructured":"DiNardo Z, Tomlinson K, Ritz A, Oesper L. Distance measures for tumor evolutionary trees. Bioinformatics. 2020;36(7):2090\u20137.","journal-title":"Bioinformatics"},{"issue":"1","key":"295_CR19","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1109\/TCBB.2020.3029689","volume":"19","author":"K Govek","year":"2020","unstructured":"Govek K, Sikes C, Zhou Y, Oesper L. GraphyC: using consensus to infer tumor evolution. IEEE\/ACM Trans Comput Biol Bioinform. 2020;19(1):465\u201378.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform"},{"issue":"1","key":"295_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13015-019-0152-9","volume":"14","author":"N Karpov","year":"2019","unstructured":"Karpov N, Malikic S, Rahman MK, Sahinalp SC. A multi-labeled tree dissimilarity measure for comparing \u201cclonal trees\u2019\u2019 of tumor progression. Algorithms Mol Biol. 2019;14(1):1\u201318.","journal-title":"Algorithms Mol Biol"},{"key":"295_CR21","doi-asserted-by":"crossref","unstructured":"Fu X, Schwartz R. ConTreeDP: a consensus method of tumor trees based on maximum directed partition support problem. In: 2021 BIBM. IEEE; 2021. p. 125\u2013130.","DOI":"10.1109\/BIBM52615.2021.9669279"},{"issue":"14","key":"295_CR22","doi-asserted-by":"publisher","first-page":"408","DOI":"10.1093\/bioinformatics\/btz312","volume":"35","author":"N Aguse","year":"2019","unstructured":"Aguse N, Qi Y, El-Kebir M. Summarizing the solution space in tumor phylogeny inference by multiple consensus trees. Bioinformatics. 2019;35(14):408\u201316.","journal-title":"Bioinformatics"},{"key":"295_CR23","doi-asserted-by":"crossref","unstructured":"Govek K, Sikes C, Oesper L. A consensus approach to infer tumor evolutionary histories. BCB; 2018. p. 63\u201372.","DOI":"10.1145\/3233547.3233584"},{"issue":"1","key":"295_CR24","first-page":"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 CB. 2021;17(1):1008400.","journal-title":"PLoS CB"},{"key":"295_CR25","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1093\/bioinformatics\/btz355","volume":"35","author":"Collaborative intra-tumor heterogeneity detection","year":"2019","unstructured":"Collaborative intra-tumor heterogeneity detection. Khakabimamaghani. Bioinformatics. 2019;35:379\u201388.","journal-title":"Bioinformatics"},{"issue":"Supplement 1","key":"295_CR26","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1093\/bioinformatics\/btaa453","volume":"36","author":"E Hodzic","year":"2020","unstructured":"Hodzic E, Shrestha R, Malikic S, Collins CC, Litchfield K, Turajlic S, et al. Identification of conserved evolutionary trajectories in tumors. Bioinformatics. 2020;36(Supplement 1):427\u201335.","journal-title":"Bioinformatics"},{"key":"295_CR27","doi-asserted-by":"publisher","DOI":"10.1017\/9781316882313","volume-title":"Computational phylogenetics: an introduction to designing methods for phylogeny estimation","author":"T Warnow","year":"2017","unstructured":"Warnow T. Computational phylogenetics: an introduction to designing methods for phylogeny estimation. Cambridge: Cambridge University Press; 2017."},{"issue":"22","key":"295_CR28","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, 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":"9","key":"295_CR29","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":"1","key":"295_CR30","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 systems. 2016;3(1):43\u201353.","journal-title":"Cell systems"},{"issue":"12","key":"295_CR31","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. https:\/\/doi.org\/10.1093\/bioinformatics\/btv261.","journal-title":"Bioinformatics"},{"issue":"16","key":"295_CR32","first-page":"3215","volume":"42","author":"A Nemirovski","year":"2004","unstructured":"Nemirovski A. Interior point polynomial time methods in convex programming. Lecture Notes. 2004;42(16):3215\u201324.","journal-title":"Lecture Notes"},{"key":"295_CR33","first-page":"376","volume":"23","author":"A Cayley","year":"1878","unstructured":"Cayley A. A theorem on trees. Quart J Math. 1878;23:376\u20138.","journal-title":"Quart J Math"},{"key":"295_CR34","doi-asserted-by":"publisher","unstructured":"Schmidt H, Qi Y, Raphael BJ, El-Kebir M. Fast tumor phylogeny regression via tree-structured dual dynamic programming. bioRxiv 2025. https:\/\/doi.org\/10.1101\/2025.01.24.634761","DOI":"10.1101\/2025.01.24.634761"},{"key":"295_CR35","doi-asserted-by":"crossref","unstructured":"Andersen M, Dahl J, Liu Z, Vandenberghe L. Interior-point methods for large-scale cone programming. Optimization for machine learning; 2011. p. 55\u201383.","DOI":"10.7551\/mitpress\/8996.003.0005"},{"key":"295_CR36","first-page":"742","volume":"27","author":"Neuer beweis eines satzes uber per mutationen","year":"1918","unstructured":"Neuer beweis eines satzes uber per mutationen. Prufer. Archiv der Mathematik und Physik. 1918;27:742\u20134.","journal-title":"Archiv der Mathematik und Physik"},{"issue":"7","key":"295_CR37","doi-asserted-by":"publisher","first-page":"2090","DOI":"10.1093\/bioinformatics\/btz869","volume":"36","author":"Z DiNardo","year":"2019","unstructured":"DiNardo Z, Tomlinson K, Ritz A, Oesper L. Distance measures for tumor evolutionary trees. Bioinformatics. 2019;36(7):2090\u20137. https:\/\/doi.org\/10.1093\/bioinformatics\/btz869.","journal-title":"Bioinformatics"},{"issue":"6","key":"295_CR38","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0020-0190(95)00110-X","volume":"55","author":"M Farach","year":"1995","unstructured":"Farach M, Przytycka TM, Thorup M. On the agreement of many trees. Inf Process Lett. 1995;55(6):297\u2013301. https:\/\/doi.org\/10.1016\/0020-0190(95)00110-X.","journal-title":"Inf Process Lett"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s13015-025-00295-5","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-025-00295-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s13015-025-00295-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T09:59:19Z","timestamp":1774519159000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1186\/s13015-025-00295-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,18]]},"references-count":38,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2026,12]]}},"alternative-id":["295"],"URL":"https:\/\/doi.org\/10.1186\/s13015-025-00295-5","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,18]]},"assertion":[{"value":"19 February 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 December 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 February 2026","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 no competing interests.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"5"}}