{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T14:28:48Z","timestamp":1776349728777,"version":"3.51.2"},"update-to":[{"DOI":"10.1371\/journal.pcbi.1012653","type":"new_version","label":"New version","source":"publisher","updated":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T00:00:00Z","timestamp":1736467200000}}],"reference-count":47,"publisher":"Public Library of Science (PLoS)","issue":"12","license":[{"start":{"date-parts":[[2024,12,30]],"date-time":"2024-12-30T00:00:00Z","timestamp":1735516800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NIH\/NCI","award":["P30CA008748"],"award-info":[{"award-number":["P30CA008748"]}]}],"content-domain":{"domain":["www.ploscompbiol.org"],"crossmark-restriction":false},"short-container-title":["PLoS Comput Biol"],"abstract":"<jats:p>Phylogenies depicting the evolutionary history of genetically heterogeneous subpopulations of cells from the same cancer, i.e., <jats:italic>cancer phylogenies<\/jats:italic>, offer valuable insights about cancer development and guide treatment strategies. Many methods exist that reconstruct cancer phylogenies using point mutations detected with bulk DNA sequencing. However, these methods become inaccurate when reconstructing phylogenies with more than 30 mutations, or, in some cases, fail to recover a phylogeny altogether. Here, we introduce <jats:italic>Orchard<\/jats:italic>, a cancer phylogeny reconstruction algorithm that is fast and accurate using up to 1000 mutations. Orchard samples without replacement from a factorized approximation of the posterior distribution over phylogenies, a novel result derived in this paper. Each factor in this approximate posterior corresponds to a conditional distribution for adding a new mutation to a partially built phylogeny. Orchard optimizes each factor sequentially, generating a sequence of incrementally larger phylogenies that ultimately culminate in a complete tree containing all mutations. Our evaluations demonstrate that Orchard outperforms state-of-the-art cancer phylogeny reconstruction methods in reconstructing more plausible phylogenies across 90 simulated cancers and 14 B-progenitor acute lymphoblastic leukemias (B-ALLs). Remarkably, Orchard accurately reconstructs cancer phylogenies using up to 1,000 mutations. Additionally, we demonstrate that the large and accurate phylogenies reconstructed by Orchard are useful for identifying patterns of somatic mutations and genetic variations among distinct cancer cell subpopulations.<\/jats:p>","DOI":"10.1371\/journal.pcbi.1012653","type":"journal-article","created":{"date-parts":[[2024,12,30]],"date-time":"2024-12-30T18:51:17Z","timestamp":1735584677000},"page":"e1012653","update-policy":"https:\/\/doi.org\/10.1371\/journal.pcbi.corrections_policy","source":"Crossref","is-referenced-by-count":7,"title":["Orchard: Building large cancer phylogenies using stochastic combinatorial search"],"prefix":"10.1371","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8460-7384","authenticated-orcid":true,"given":"Ethan","family":"Kulman","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rui","family":"Kuang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2760-6999","authenticated-orcid":true,"given":"Quaid","family":"Morris","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"340","published-online":{"date-parts":[[2024,12,30]]},"reference":[{"issue":"1","key":"pcbi.1012653.ref001","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/S0092-8674(00)81683-9","article-title":"The Hallmarks of Cancer","volume":"100","author":"D Hanahan","year":"2000","journal-title":"Cell"},{"issue":"4260","key":"pcbi.1012653.ref002","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1126\/science.959840","article-title":"The clonal evolution of tumor cell populations","volume":"194","author":"PC Nowell","year":"1976","journal-title":"Science (New York, NY)"},{"issue":"7381","key":"pcbi.1012653.ref003","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1038\/nature10762","article-title":"Clonal evolution in cancer","volume":"481","author":"M Greaves","year":"2012","journal-title":"Nature"},{"issue":"7793","key":"pcbi.1012653.ref004","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1038\/s41586-019-1907-7","article-title":"The evolutionary history of 2,658 cancers","volume":"578","author":"M Gerstung","year":"2020","journal-title":"Nature"},{"issue":"8","key":"pcbi.1012653.ref005","doi-asserted-by":"crossref","first-page":"2239","DOI":"10.1016\/j.cell.2021.03.009","article-title":"Characterizing genetic intra-tumor heterogeneity across 2,658 human cancer genomes","volume":"184","author":"SC Dentro","year":"2021","journal-title":"Cell"},{"issue":"1","key":"pcbi.1012653.ref006","doi-asserted-by":"crossref","first-page":"12475","DOI":"10.1038\/ncomms12475","article-title":"Genetic hierarchy and temporal variegation in the clonal history of acute myeloid leukaemia","volume":"7","author":"P Hirsch","year":"2016","journal-title":"Nature Communications"},{"issue":"4","key":"pcbi.1012653.ref007","doi-asserted-by":"crossref","first-page":"a027060","DOI":"10.1101\/cshperspect.a027060","article-title":"Order Matters: The Order of Somatic Mutations Influences Cancer Evolution","volume":"7","author":"DG Kent","year":"2017","journal-title":"Cold Spring Harbor Perspectives in Medicine"},{"issue":"4","key":"pcbi.1012653.ref008","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1038\/s41576-022-00458-9","article-title":"Using tumour phylogenies to identify drivers","volume":"23","author":"L Koch","year":"2022","journal-title":"Nature Reviews Genetics"},{"issue":"8","key":"pcbi.1012653.ref009","doi-asserted-by":"crossref","first-page":"639","DOI":"10.1016\/j.tig.2018.05.007","article-title":"Harnessing Tumor Evolution to Circumvent Resistance","volume":"34","author":"KL Pogrebniak","year":"2018","journal-title":"Trends in genetics: TIG"},{"issue":"4","key":"pcbi.1012653.ref010","doi-asserted-by":"crossref","first-page":"390","DOI":"10.2307\/2412432","article-title":"Consensus Techniques and the Comparison of Taxonomic Trees","volume":"21","author":"EN Adams","year":"1972","journal-title":"Systematic Zoology"},{"issue":"5","key":"pcbi.1012653.ref011","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":"S Nik-Zainal","year":"2012","journal-title":"Cell"},{"issue":"22","key":"pcbi.1012653.ref012","doi-asserted-by":"crossref","first-page":"2109","DOI":"10.1056\/NEJMoa1616288","article-title":"Tracking the Evolution of Non\u2013Small-Cell Lung Cancer","volume":"376","author":"M Jamal-Hanjani","year":"2017","journal-title":"New England Journal of Medicine"},{"issue":"1","key":"pcbi.1012653.ref013","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1038\/s41467-022-35727-y","article-title":"Germline TP53 mutations undergo copy number gain years prior to tumor diagnosis","volume":"14","author":"N Light","year":"2023","journal-title":"Nature Communications"},{"issue":"6","key":"pcbi.1012653.ref014","doi-asserted-by":"crossref","first-page":"792","DOI":"10.1158\/2159-8290.CD-19-1508","article-title":"The Evolutionary Origins of Recurrent Pancreatic Cancer","volume":"10","author":"H Sakamoto","year":"2020","journal-title":"Cancer Discovery"},{"issue":"20","key":"pcbi.1012653.ref015","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":"A Schuh","year":"2012","journal-title":"Blood"},{"key":"pcbi.1012653.ref016","first-page":"1","article-title":"The clinical utility of integrative genomics in childhood cancer extends beyond targetable mutations","author":"A Villani","year":"2022","journal-title":"Nature Cancer"},{"issue":"5","key":"pcbi.1012653.ref017","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1038\/s41588-018-0106-z","article-title":"Inferring parsimonious migration histories for metastatic cancers","volume":"50","author":"M El-Kebir","year":"2018","journal-title":"Nature Genetics"},{"issue":"3","key":"pcbi.1012653.ref018","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1016\/j.cell.2018.03.043","article-title":"Deterministic Evolutionary Trajectories Influence Primary Tumor Growth: TRACERx Renal","volume":"173","author":"S Turajlic","year":"2018","journal-title":"Cell"},{"issue":"1","key":"pcbi.1012653.ref019","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1186\/s13073-017-0424-2","article-title":"Analysis of 100,000 human cancer genomes reveals the landscape of tumor mutational burden","volume":"9","author":"ZR Chalmers","year":"2017","journal-title":"Genome Medicine"},{"issue":"1","key":"pcbi.1012653.ref020","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1002\/net.3230210104","article-title":"Efficient algorithms for inferring evolutionary trees","volume":"21","author":"D Gusfield","year":"1991","journal-title":"Networks"},{"issue":"12","key":"pcbi.1012653.ref021","doi-asserted-by":"crossref","first-page":"i62","DOI":"10.1093\/bioinformatics\/btv261","article-title":"Reconstruction of clonal trees and tumor composition from multi-sample sequencing data","volume":"31","author":"M El-Kebir","year":"2015","journal-title":"Bioinformatics"},{"issue":"1","key":"pcbi.1012653.ref022","doi-asserted-by":"crossref","first-page":"e1008400","DOI":"10.1371\/journal.pcbi.1008400","article-title":"Reconstructing tumor evolutionary histories and clone trees in polynomial-time with SubMARine","volume":"17","author":"LK Sundermann","year":"2021","journal-title":"PLOS Computational Biology"},{"issue":"1","key":"pcbi.1012653.ref023","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1142\/S0219720003000174","article-title":"Efficient reconstruction of haplotype structure via perfect phylogeny","volume":"1","author":"E Eskin","year":"2003","journal-title":"Journal of Bioinformatics and Computational Biology"},{"key":"pcbi.1012653.ref024","doi-asserted-by":"crossref","unstructured":"Gusfield D. Haplotyping as perfect phylogeny: conceptual framework and efficient solutions. In: Proceedings of the sixth annual international conference on Computational biology. RECOMB\u201902. New York, NY, USA: Association for Computing Machinery; 2002. p. 166\u2013175. Available from: https:\/\/doi.org\/10.1145\/565196.565218.","DOI":"10.1145\/565196.565218"},{"issue":"3","key":"pcbi.1012653.ref025","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1158\/2643-3230.BCD-21-0092","article-title":"Reconstructing Complex Cancer Evolutionary Histories from Multiple Bulk DNA Samples Using Pairtree","volume":"3","author":"JA Wintersinger","year":"2022","journal-title":"Blood Cancer Discovery"},{"issue":"6","key":"pcbi.1012653.ref026","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1016\/j.cels.2019.05.010","article-title":"CALDER: Inferring Phylogenetic Trees from Longitudinal Tumor Samples","volume":"8","author":"MA Myers","year":"2019","journal-title":"Cell Systems"},{"issue":"9","key":"pcbi.1012653.ref027","doi-asserted-by":"crossref","first-page":"898","DOI":"10.1038\/s41588-020-0675-5","article-title":"Subclonal reconstruction of tumors by using machine learning and population genetics","volume":"52","author":"G Caravagna","year":"2020","journal-title":"Nature Genetics"},{"issue":"1","key":"pcbi.1012653.ref028","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1186\/s12859-020-03919-2","article-title":"PyClone-VI: scalable inference of clonal population structures using whole genome data","volume":"21","author":"S Gillis","year":"2020","journal-title":"BMC Bioinformatics"},{"issue":"8","key":"pcbi.1012653.ref029","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":"CA Miller","year":"2014","journal-title":"PLOS Computational Biology"},{"issue":"1","key":"pcbi.1012653.ref030","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1038\/s41587-019-0364-z","article-title":"A community effort to create standards for evaluating tumor subclonal reconstruction","volume":"38","author":"A Salcedo","year":"2020","journal-title":"Nature Biotechnology"},{"issue":"7","key":"pcbi.1012653.ref031","doi-asserted-by":"crossref","first-page":"1015","DOI":"10.1038\/ng.3891","article-title":"Between-region genetic divergence reflects the mode and tempo of tumor evolution","volume":"49","author":"R Sun","year":"2017","journal-title":"Nature Genetics"},{"issue":"3","key":"pcbi.1012653.ref032","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1038\/ng.3489","article-title":"Identification of neutral tumor evolution across cancer types","volume":"48","author":"MJ Williams","year":"2016","journal-title":"Nature Genetics"},{"issue":"14","key":"pcbi.1012653.ref033","doi-asserted-by":"crossref","first-page":"i152","DOI":"10.1093\/bioinformatics\/btx270","article-title":"Tumor phylogeny inference using tree-constrained importance sampling","volume":"33","author":"G Satas","year":"2017","journal-title":"Bioinformatics"},{"issue":"1","key":"pcbi.1012653.ref034","doi-asserted-by":"crossref","first-page":"7244","DOI":"10.1038\/s41467-021-27472-5","article-title":"Clonal architecture predicts clinical outcomes and drug sensitivity in acute myeloid leukemia","volume":"12","author":"BA Benard","year":"2021","journal-title":"Nature Communications"},{"issue":"7","key":"pcbi.1012653.ref035","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1056\/NEJMoa1412098","article-title":"Effect of Mutation Order on Myeloproliferative Neoplasms","volume":"372","author":"CA Ortmann","year":"2015","journal-title":"New England Journal of Medicine"},{"key":"pcbi.1012653.ref036","first-page":"1","article-title":"Mutation order in acute myeloid leukemia identifies uncommon patterns of evolution and illuminates phenotypic heterogeneity","author":"M Schwede","year":"2024","journal-title":"Leukemia"},{"key":"pcbi.1012653.ref037","unstructured":"Kool W, van Hoof H, Welling M. Stochastic Beams and Where to Find Them: The Gumbel-Top-k Trick for Sampling Sequences Without Replacement; 2019. Available from: http:\/\/arxiv.org\/abs\/1903.06059."},{"issue":"47","key":"pcbi.1012653.ref038","first-page":"1","article-title":"Ancestral Gumbel-Top-k Sampling for Sampling Without Replacement","volume":"21","author":"W Kool","year":"2020","journal-title":"Journal of Machine Learning Research"},{"key":"pcbi.1012653.ref039","unstructured":"Paulus MB, Choi D, Tarlow D, Krause A, Maddison CJ. Gradient Estimation with Stochastic Softmax Tricks; 2021. Available from: http:\/\/arxiv.org\/abs\/2006.08063."},{"issue":"2","key":"pcbi.1012653.ref040","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1038\/s41592-020-01013-2","article-title":"A practical guide to cancer subclonal reconstruction from DNA sequencing","volume":"18","author":"M Tarabichi","year":"2021","journal-title":"Nature Methods"},{"key":"pcbi.1012653.ref041","first-page":"376","article-title":"A theorem on trees","volume":"XXIII","author":"A Cayley","year":"1889","journal-title":"Quarterly Journal of Pure and Applied Mathematics"},{"key":"pcbi.1012653.ref042","unstructured":"Maddison CJ, Tarlow D, Minka T. A\\ast Sampling. In: Advances in Neural Information Processing Systems. vol. 27. Curran Associates, Inc.; 2014. Available from: https:\/\/papers.nips.cc\/paper_files\/paper\/2014\/hash\/309fee4e541e51de2e41f21bebb342aa-Abstract.html."},{"key":"pcbi.1012653.ref043","unstructured":"Gumbel EJ. Statistical Theory of Extreme Values and Some Practical Applications. A Series of Lectures. National Bureau of Standards, Washington, D. C. Applied Mathematics Div.; 1954. PB175818. Available from: https:\/\/ntrl.ntis.gov\/NTRL\/dashboard\/searchResults\/titleDetail\/PB175818.xhtml."},{"key":"pcbi.1012653.ref044","unstructured":"Jia B, Ray S, Safavi S, Bento J. Efficient Projection onto the Perfect Phylogeny Model. In: Advances in Neural Information Processing Systems. vol. 31. Curran Associates, Inc.; 2018. Available from: https:\/\/proceedings.neurips.cc\/paper\/2018\/hash\/d198bd736a97e7cecfdf8f4f2027ef80-Abstract.html."},{"key":"pcbi.1012653.ref045","unstructured":"Ray S, Jia B, Safavi S, van Opijnen T, Isberg R, Rosch J, et al. Exact inference under the perfect phylogeny model; 2019. Available from: http:\/\/arxiv.org\/abs\/1908.08623."},{"key":"pcbi.1012653.ref046","unstructured":"Kim Y, Kwon S, Choi H. Consistent Model Selection Criteria on High Dimensions;."},{"issue":"4","key":"pcbi.1012653.ref047","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1158\/2159-8290.CD-19-1059","article-title":"Relapse-Fated Latent Diagnosis Subclones in Acute B Lineage Leukemia Are Drug Tolerant and Possess Distinct Metabolic Programs","volume":"10","author":"SM Dobson","year":"2020","journal-title":"Cancer Discovery"}],"updated-by":[{"DOI":"10.1371\/journal.pcbi.1012653","type":"new_version","label":"New version","source":"publisher","updated":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T00:00:00Z","timestamp":1736467200000}}],"container-title":["PLOS Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pcbi.1012653","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T20:23:23Z","timestamp":1736540603000},"score":1,"resource":{"primary":{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pcbi.1012653"}},"subtitle":[],"editor":[{"given":"Mohammed","family":"El-Kebir","sequence":"first","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2024,12,30]]},"references-count":47,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2024,12,30]]}},"URL":"https:\/\/doi.org\/10.1371\/journal.pcbi.1012653","relation":{"new_version":[{"id-type":"doi","id":"10.1371\/journal.pcbi.1012653","asserted-by":"object"}]},"ISSN":["1553-7358"],"issn-type":[{"value":"1553-7358","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,30]]}}}