{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T00:24:09Z","timestamp":1773275049981,"version":"3.50.1"},"reference-count":42,"publisher":"Oxford University Press (OUP)","issue":"3","license":[{"start":{"date-parts":[[2020,8,17]],"date-time":"2020-08-17T00:00:00Z","timestamp":1597622400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"European Union\u2019s Horizon 2020 research and innovation programme"},{"name":"Marie Sk\u0142odowska-Curie","award":["872539"],"award-info":[{"award-number":["872539"]}]},{"DOI":"10.13039\/100000002","name":"NIH","doi-asserted-by":"publisher","award":["1T32GM083937"],"award-info":[{"award-number":["1T32GM083937"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"US National Science Foundation","doi-asserted-by":"crossref","award":["IIS-1840275"],"award-info":[{"award-number":["IIS-1840275"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,4,20]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>In recent years, the well-known Infinite Sites Assumption has been a fundamental feature of computational methods devised for reconstructing tumor phylogenies and inferring cancer progressions. However, recent studies leveraging single-cell sequencing (SCS) techniques have shown evidence of the widespread recurrence and, especially, loss of mutations in several tumor samples. While there exist established computational methods that infer phylogenies with mutation losses, there remain some advancements to be made.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>We present Simulated Annealing Single-Cell inference (SASC): a new and robust approach based on simulated annealing for the inference of cancer progression from SCS datasets. In particular, we introduce an extension of the model of evolution where mutations are only accumulated, by allowing also a limited amount of mutation loss in the evolutionary history of the tumor: the Dollo-k model. We demonstrate that SASC achieves high levels of accuracy when tested on both simulated and real datasets and in comparison with some other available methods.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and implementation<\/jats:title>\n                    <jats:p>The SASC tool is open source and available at https:\/\/github.com\/sciccolella\/sasc.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Supplementary information<\/jats:title>\n                    <jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btaa722","type":"journal-article","created":{"date-parts":[[2020,8,11]],"date-time":"2020-08-11T17:48:09Z","timestamp":1597168089000},"page":"326-333","source":"Crossref","is-referenced-by-count":37,"title":["Inferring cancer progression from Single-Cell Sequencing while allowing mutation losses"],"prefix":"10.1093","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6469-4887","authenticated-orcid":false,"given":"Simone","family":"Ciccolella","sequence":"first","affiliation":[{"name":"Department of Informatics, Systems and Communication, University of Milano-Bicocca , Milan, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Camir","family":"Ricketts","sequence":"additional","affiliation":[{"name":"Department of Physiology and Biophysics, Tri-I Computational Biology & Medicine Graduate Program, Weill Cornell Medicine of Cornell University , New York, NY 10021, USA"},{"name":"Institute for Computational Biomedicine, Englander Institute for Precision Medicine, The Meyer Cancer Center, Department of Physiology and Biophysics, Weill Cornell Medicine of Cornell University , New York City, NY 10021, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mauricio","family":"Soto Gomez","sequence":"additional","affiliation":[{"name":"Department of Informatics, Systems and Communication, University of Milano-Bicocca , Milan, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Murray","family":"Patterson","sequence":"additional","affiliation":[{"name":"Department of Informatics, Systems and Communication, University of Milano-Bicocca , Milan, Italy"},{"name":"Department of Computer Science, College of Arts and Sciences, Georgia State University , Atlanta, GA 30303, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dana","family":"Silverbush","sequence":"additional","affiliation":[{"name":"Department of Pathology and Center for Cancer Research, Massachusetts General Hospital and Harvard Medical School , Boston, MA 02114, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paola","family":"Bonizzoni","sequence":"additional","affiliation":[{"name":"Department of Informatics, Systems and Communication, University of Milano-Bicocca , Milan, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Iman","family":"Hajirasouliha","sequence":"additional","affiliation":[{"name":"Institute for Computational Biomedicine, Englander Institute for Precision Medicine, The Meyer Cancer Center, Department of Physiology and Biophysics, Weill Cornell Medicine of Cornell University , New York City, NY 10021, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5584-3089","authenticated-orcid":false,"given":"Gianluca","family":"Della Vedova","sequence":"additional","affiliation":[{"name":"Department of Informatics, Systems and Communication, University of Milano-Bicocca , Milan, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2020,8,17]]},"reference":[{"key":"2023051604083008500_btaa722-B1","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/j.tcs.2012.05.035","article-title":"The binary perfect phylogeny with persistent characters","volume":"454","author":"Bonizzoni","year":"2012","journal-title":"Theor. Comput. Sci"},{"key":"2023051604083008500_btaa722-B2","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1016\/j.tcs.2016.08.015","article-title":"A colored graph approach to perfect phylogeny with persistent characters","volume":"658","author":"Bonizzoni","year":"2017","journal-title":"Theor. Comput. Sci"},{"key":"2023051604083008500_btaa722-B3","doi-asserted-by":"crossref","first-page":"1410","DOI":"10.1109\/TCBB.2018.2865729","article-title":"Does relaxing the infinite sites assumption give better tumor phylogenies? An ILP-based comparative approach","volume":"16","author":"Bonizzoni","year":"2018","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform"},{"key":"2023051604083008500_btaa722-B4","doi-asserted-by":"crossref","first-page":"14944","DOI":"10.1038\/ncomms14944","article-title":"Phylogenetic analysis of metastatic progression in breast cancer using somatic mutations and copy number aberrations","volume":"8","author":"Brown","year":"2017","journal-title":"Nat. Commun"},{"key":"2023051604083008500_btaa722-B5","first-page":"3","author":"Della Vedova","year":"2017"},{"key":"2023051604083008500_btaa722-B6","doi-asserted-by":"crossref","first-page":"1718","DOI":"10.1016\/j.celrep.2019.09.082","article-title":"Doubletdecon: deconvoluting doublets from single-cell RNA-sequencing data","volume":"29","author":"DePasquale","year":"2019","journal-title":"Cell Rep"},{"key":"2023051604083008500_btaa722-B7","doi-asserted-by":"crossref","first-page":"i671","DOI":"10.1093\/bioinformatics\/bty589","article-title":"SphyR: tumor phylogeny estimation from single-cell sequencing data under loss and error","volume":"34","author":"El-Kebir","year":"2018","journal-title":"Bioinformatics"},{"key":"2023051604083008500_btaa722-B8","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/j.cels.2016.07.004","article-title":"Inferring the mutational history of a tumor using multi-state perfect phylogeny mixtures","volume":"3","author":"El-Kebir","year":"2016","journal-title":"Cell Syst"},{"key":"2023051604083008500_btaa722-B9","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1093\/sysbio\/26.1.77","article-title":"Phylogenetic analysis under Dollo\u2019s law","volume":"26","author":"Farris","year":"1977","journal-title":"Syst. Biol"},{"key":"2023051604083008500_btaa722-B10","doi-asserted-by":"crossref","first-page":"17947","DOI":"10.1073\/pnas.1420822111","article-title":"Dissecting the clonal origins of childhood acute lymphoblastic leukemia by single-cell genomics","volume":"111","author":"Gawad","year":"2014","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023051604083008500_btaa722-B11","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/S0166-218X(96)00060-1","article-title":"Minimizing phylogenetic number to find good evolutionary trees","volume":"71","author":"Goldberg","year":"1996","journal-title":"Discrete Appl. Math"},{"key":"2023051604083008500_btaa722-B12","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":"2023051604083008500_btaa722-B13","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":"2023051604083008500_btaa722-B14","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1038\/s41586-019-1434-6","article-title":"Resolving medulloblastoma cellular architecture by single-cell genomics","volume":"572","author":"Hovestadt","year":"2019","journal-title":"Nature"},{"key":"2023051604083008500_btaa722-B15","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1186\/s13059-016-0936-x","article-title":"Tree inference for single-cell data","volume":"17","author":"Jahn","year":"2016","journal-title":"Genome Biol"},{"key":"2023051604083008500_btaa722-B16","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":"2023051604083008500_btaa722-B17","first-page":"22:1","volume-title":"18th International Workshop on Algorithms in Bioinformatics (WABI 2018). Leibniz International Proceedings in Informatics (LIPIcs)","author":"Karpov","year":"2018"},{"key":"2023051604083008500_btaa722-B18","doi-asserted-by":"crossref","first-page":"893","DOI":"10.1093\/genetics\/61.4.893","article-title":"The number of heterozygous nucleotide sites maintained in a finite population due to steady flux of mutations","volume":"61","author":"Kimura","year":"1969","journal-title":"Genetics"},{"key":"2023051604083008500_btaa722-B19","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","article-title":"Optimization by simulated annealing","volume":"220","author":"Kirkpatrick","year":"1983","journal-title":"Science"},{"key":"2023051604083008500_btaa722-B20","doi-asserted-by":"crossref","first-page":"1885","DOI":"10.1101\/gr.220707.117","article-title":"Single-cell sequencing data reveal widespread recurrence and loss of mutational hits in the life histories of tumors","volume":"27","author":"Kuipers","year":"2017","journal-title":"Genome Res"},{"key":"2023051604083008500_btaa722-B21","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":"2023051604083008500_btaa722-B22","journal-title":"et al."},{"key":"2023051604083008500_btaa722-B23","doi-asserted-by":"crossref","first-page":"1860","DOI":"10.1101\/gr.234435.118","article-title":"PhISCS: a combinatorial approach for subperfect tumor phylogeny reconstruction via integrative use of single-cell and bulk sequencing data","volume":"29","author":"Malikic","year":"2019","journal-title":"Genome Res"},{"key":"2023051604083008500_btaa722-B24","doi-asserted-by":"crossref","first-page":"2377","DOI":"10.1214\/16-AOAS986","article-title":"A phylogenetic latent feature model for clonal deconvolution","volume":"10","author":"Marass","year":"2016","journal-title":"Ann. Appl. Stat"},{"key":"2023051604083008500_btaa722-B25","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1038\/nature16478","article-title":"Divergent clonal selection dominates medulloblastoma at recurrence","volume":"529","author":"Morrissy","year":"2016","journal-title":"Nature"},{"key":"2023051604083008500_btaa722-B26","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1186\/s13059-015-0647-8","article-title":"Fast and scalable inference of multi-sample cancer lineages","volume":"16","author":"Popic","year":"2015","journal-title":"Genome Biol"},{"key":"2023051604083008500_btaa722-B27","doi-asserted-by":"crossref","DOI":"10.1186\/s12859-019-2795-4","article-title":"Learning mutational graphs of individual tumor evolution from multi-sample sequencing data","volume":"20","author":"Ramazzotti","year":"2019","journal-title":"BMC Bioinformatics.,"},{"key":"2023051604083008500_btaa722-B28","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780199297306.003.0011","volume-title":"Dollo Parsimony and the Reconstruction of Genome Evolution","author":"Rogozin","year":"2006"},{"key":"2023051604083008500_btaa722-B29","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1186\/s13059-016-0929-9","article-title":"OncoNEM: inferring tumor evolution from single-cell sequencing data","volume":"17","author":"Ross","year":"2016","journal-title":"Genome Biol"},{"key":"2023051604083008500_btaa722-B30","doi-asserted-by":"crossref","first-page":"573","DOI":"10.1038\/nmeth.3867","article-title":"Clonal genotype and population structure inference from single-cell tumor sequencing","volume":"13","author":"Roth","year":"2016","journal-title":"Nat. Methods"},{"key":"2023051604083008500_btaa722-B31","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1186\/s13059-017-1169-3","article-title":"ddClone: joint statistical inference of clonal populations from single cell and bulk tumour sequencing data","volume":"18","author":"Salehi","year":"2017","journal-title":"Genome Biol"},{"key":"2023051604083008500_btaa722-B32","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":"Satas","year":"2017","journal-title":"Bioinformatics"},{"key":"2023051604083008500_btaa722-B33","doi-asserted-by":"crossref","first-page":"5144","DOI":"10.1038\/s41467-018-07627-7","article-title":"Single-cell mutation identification via phylogenetic inference","volume":"9","author":"Singer","year":"2018","journal-title":"Nat. Commun"},{"key":"2023051604083008500_btaa722-B34","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":"2023051604083008500_btaa722-B35","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1038\/nature20123","article-title":"Single-cell RNA-seq supports a developmental hierarchy in human oligodendroglioma","volume":"539","author":"Tirosh","year":"2016","journal-title":"Nature"},{"key":"2023051604083008500_btaa722-B36","doi-asserted-by":"crossref","first-page":"282","DOI":"10.1186\/s12859-019-2824-3","article-title":"BAMSE: Bayesian model selection for tumor phylogeny inference among multiple samples","volume":"20","author":"Toosi","year":"2019","journal-title":"BMC Bioinformatics"},{"key":"2023051604083008500_btaa722-B37","doi-asserted-by":"crossref","first-page":"768","DOI":"10.1038\/ng.3590","article-title":"Clonal evolution of glioblastoma under therapy","volume":"48","author":"Wang","year":"2016","journal-title":"Nat. Genet"},{"key":"2023051604083008500_btaa722-B38","doi-asserted-by":"crossref","first-page":"742","DOI":"10.1093\/bioinformatics\/btz676","article-title":"Accurate and efficient cell lineage tree inference from noisy single cell data: the maximum likelihood perfect phylogeny approach","volume":"36","author":"Wu","year":"2019","journal-title":"Bioinformatics"},{"key":"2023051604083008500_btaa722-B39","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1186\/s13059-015-0592-6","article-title":"Bitphylogeny: a probabilistic framework for reconstructing intra-tumor phylogenies","volume":"16","author":"Yuan","year":"2015","journal-title":"Genome Biol"},{"key":"2023051604083008500_btaa722-B40","doi-asserted-by":"crossref","first-page":"505","DOI":"10.1038\/nmeth.3835","article-title":"Monovar: single-nucleotide variant detection in single cells","volume":"13","author":"Zafar","year":"2016","journal-title":"Nat. Methods"},{"key":"2023051604083008500_btaa722-B41","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1186\/s13059-017-1311-2","article-title":"SiFit: inferring tumor trees from single-cell sequencing data under finite-sites models","volume":"18","author":"Zafar","year":"2017","journal-title":"Genome Biol"},{"key":"2023051604083008500_btaa722-B42","doi-asserted-by":"crossref","first-page":"1847","DOI":"10.1101\/gr.243121.118","article-title":"SiCloneFit: Bayesian inference of population structure, genotype, and phylogeny of tumor clones from single-cell genome sequencing data","volume":"29","author":"Zafar","year":"2019","journal-title":"Genome Res"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btaa722\/34415082\/btaa722.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/37\/3\/326\/50325906\/btaa722.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/37\/3\/326\/50325906\/btaa722.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T00:09:29Z","timestamp":1684195769000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/37\/3\/326\/5893545"}},"subtitle":[],"editor":[{"given":"Pier","family":"Luigi Martelli","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2020,8,17]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,4,20]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btaa722","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/268243","asserted-by":"object"}]},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2021,2,1]]},"published":{"date-parts":[[2020,8,17]]}}}