{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T06:13:39Z","timestamp":1772172819842,"version":"3.50.1"},"update-to":[{"DOI":"10.1371\/journal.pcbi.1009100","type":"new_version","label":"New version","source":"publisher","updated":{"date-parts":[[2022,8,30]],"date-time":"2022-08-30T00:00:00Z","timestamp":1661817600000}}],"reference-count":37,"publisher":"Public Library of Science (PLoS)","issue":"8","license":[{"start":{"date-parts":[[2022,8,11]],"date-time":"2022-08-11T00:00:00Z","timestamp":1660176000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Helmholtz Association","award":["Sparse2Big ZT-I-0007"],"award-info":[{"award-number":["Sparse2Big ZT-I-0007"]}]},{"name":"Helmholtz Association","award":["Sparse2Big ZT-I-0007"],"award-info":[{"award-number":["Sparse2Big ZT-I-0007"]}]},{"name":"Helmholtz Association","award":["Sparse2Big ZT-I-0007"],"award-info":[{"award-number":["Sparse2Big ZT-I-0007"]}]}],"content-domain":{"domain":["www.ploscompbiol.org"],"crossmark-restriction":false},"short-container-title":["PLoS Comput Biol"],"abstract":"<jats:p>Single-cell genome sequencing provides a highly granular view of biological systems but is affected by high error rates, allelic amplification bias, and uneven genome coverage. This creates a need for data-specific computational methods, for purposes such as for cell lineage tree inference. The objective of cell lineage tree reconstruction is to infer the evolutionary process that generated a set of observed cell genomes. Lineage trees may enable a better understanding of tumor formation and growth, as well as of organ development for healthy body cells. We describe a method, Scelestial, for lineage tree reconstruction from single-cell data, which is based on an approximation algorithm for the Steiner tree problem and is a generalization of the neighbor-joining method. We adapt the algorithm to efficiently select a limited subset of potential sequences as internal nodes, in the presence of missing values, and to minimize cost by lineage tree-based missing value imputation. In a comparison against seven state-of-the-art single-cell lineage tree reconstruction algorithms\u2014BitPhylogeny, OncoNEM, SCITE, SiFit, SASC, SCIPhI, and SiCloneFit\u2014on simulated and real single-cell tumor samples, Scelestial performed best at reconstructing trees in terms of accuracy and run time. Scelestial has been implemented in C++. It is also available as an R package named RScelestial.<\/jats:p>","DOI":"10.1371\/journal.pcbi.1009100","type":"journal-article","created":{"date-parts":[[2022,8,11]],"date-time":"2022-08-11T13:46:20Z","timestamp":1660225580000},"page":"e1009100","update-policy":"https:\/\/doi.org\/10.1371\/journal.pcbi.corrections_policy","source":"Crossref","is-referenced-by-count":0,"title":["Scelestial: Fast and accurate single-cell lineage tree inference based on a Steiner tree approximation algorithm"],"prefix":"10.1371","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9976-1138","authenticated-orcid":true,"given":"Mohammad-Hadi","family":"Foroughmand-Araabi","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6275-2783","authenticated-orcid":true,"given":"Sama","family":"Goliaei","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2370-3430","authenticated-orcid":true,"given":"Alice C.","family":"McHardy","sequence":"additional","affiliation":[]}],"member":"340","published-online":{"date-parts":[[2022,8,11]]},"reference":[{"issue":"1","key":"pcbi.1009100.ref001","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s13059-020-1926-6","article-title":"Eleven grand challenges in single-cell data science","volume":"21","author":"D L\u00e4hnemann","year":"2020","journal-title":"Genome Biology"},{"issue":"2","key":"pcbi.1009100.ref002","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1016\/j.bbcan.2017.02.001","article-title":"Advances in understanding tumour evolution through single-cell sequencing","volume":"1867","author":"J Kuipers","year":"2017","journal-title":"Biochimica et Biophysica Acta (BBA)\u2014Reviews on Cancer"},{"issue":"1","key":"pcbi.1009100.ref003","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1186\/1471-2105-15-27","article-title":"Using single cell sequencing data to model the evolutionary history of a tumor","volume":"15","author":"KI Kim","year":"2014","journal-title":"BMC Bioinformatics"},{"issue":"1","key":"pcbi.1009100.ref004","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":"K Yuan","year":"2015","journal-title":"Genome Biology"},{"issue":"1","key":"pcbi.1009100.ref005","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":"EM Ross","year":"2016","journal-title":"Genome Biology"},{"issue":"1","key":"pcbi.1009100.ref006","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":"K Jahn","year":"2016","journal-title":"Genome Biology"},{"issue":"1","key":"pcbi.1009100.ref007","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":"H Zafar","year":"2017","journal-title":"Genome Biology"},{"key":"pcbi.1009100.ref008","unstructured":"Inferring cancer progression from single-cell sequencing while allowing mutation losses; 2018."},{"issue":"17","key":"pcbi.1009100.ref009","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":"M El-Kebir","year":"2018","journal-title":"Bioinformatics"},{"issue":"1","key":"pcbi.1009100.ref010","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1038\/s41467-018-07627-7","article-title":"Single-cell mutation identification via phylogenetic inference","volume":"9","author":"J Singer","year":"2018","journal-title":"Nature Communications"},{"issue":"11","key":"pcbi.1009100.ref011","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":"H Zafar","year":"2019","journal-title":"Genome Research"},{"issue":"1","key":"pcbi.1009100.ref012","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1038\/s41467-019-10737-5","article-title":"Integrative inference of subclonal tumour evolution from single-cell and bulk sequencing data","volume":"10","author":"S Malikic","year":"2019","journal-title":"Nature communications"},{"issue":"11","key":"pcbi.1009100.ref013","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":"S Malikic","year":"2019","journal-title":"Genome Research"},{"issue":"1","key":"pcbi.1009100.ref014","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1186\/1748-7188-8-3","article-title":"A mixed integer linear programming model to reconstruct phylogenies from single nucleotide polymorphism haplotypes under the maximum parsimony criterion","volume":"8","author":"D Catanzaro","year":"2013","journal-title":"Algorithms for Molecular Biology"},{"issue":"3","key":"pcbi.1009100.ref015","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1109\/TCBB.2008.26","article-title":"Mixed integer linear programming for maximum-parsimony phylogeny inference","volume":"5","author":"S Sridhar","year":"2008","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics"},{"issue":"9","key":"pcbi.1009100.ref016","doi-asserted-by":"crossref","first-page":"1265","DOI":"10.1109\/43.784119","article-title":"On wirelength estimations for row-based placement","volume":"18","author":"AE Caldwell","year":"1999","journal-title":"IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems"},{"key":"pcbi.1009100.ref017","unstructured":"Peyer S. Shortest paths and Steiner trees in VLSI routing [PhD dissertation]. PhD thesis, Research Institute for Discrete Mathematics, University of Bonn; 2007."},{"issue":"1","key":"pcbi.1009100.ref018","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0116001","article-title":"Steiner minimal trees","volume":"16","author":"EN Gilbert","year":"1968","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"pcbi.1009100.ref019","volume-title":"The Steiner ratio","author":"D Cieslik","year":"2013"},{"key":"pcbi.1009100.ref020","volume-title":"Advances in Steiner trees","author":"DZ Du","year":"2013"},{"key":"pcbi.1009100.ref021","volume-title":"Minimal networks: The Steiner problem and its generalizations","author":"AO Ivanov","year":"1994"},{"key":"pcbi.1009100.ref022","volume-title":"The Steiner tree problem: a tour through graphs, algorithms, and complexity","author":"HJ Pr\u00f6mel","year":"2012"},{"issue":"1","key":"pcbi.1009100.ref023","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1109\/TCBB.2008.13","article-title":"Approximate maximum parsimony and ancestral maximum likelihood","volume":"7","author":"N Alon","year":"2008","journal-title":"IEEE\/ACM Transactions on Computational Biology and Bioinformatics"},{"issue":"3","key":"pcbi.1009100.ref024","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1006\/jagm.1994.1041","article-title":"Improved approximations for the Steiner tree problem","volume":"17","author":"P Berman","year":"1994","journal-title":"Journal of Algorithms"},{"issue":"8","key":"pcbi.1009100.ref025","doi-asserted-by":"crossref","first-page":"1287","DOI":"10.1101\/gr.209973.116","article-title":"Single-cell DNA sequencing reveals a late-dissemination model in metastatic colorectal cancer","volume":"27","author":"ML Leung","year":"2017","journal-title":"Genome Research"},{"issue":"1","key":"pcbi.1009100.ref026","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1186\/2047-217X-1-12","article-title":"Single-cell sequencing analysis characterizes common and cell-lineage-specific mutations in a muscle-invasive bladder cancer","volume":"1","author":"Y Li","year":"2012","journal-title":"GigaScience"},{"issue":"D1","key":"pcbi.1009100.ref027","doi-asserted-by":"crossref","first-page":"D941","DOI":"10.1093\/nar\/gky1015","article-title":"COSMIC: the catalogue of somatic mutations in cancer","volume":"47","author":"JG Tate","year":"2019","journal-title":"Nucleic acids research"},{"issue":"3","key":"pcbi.1009100.ref028","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1093\/sysbio\/42.3.382","article-title":"Trees from languages and genes are very similar","volume":"42","author":"D Penny","year":"1993","journal-title":"Systematic biology"},{"key":"pcbi.1009100.ref029","unstructured":"Bourque M. Arbres de Steiner et r\u00e9seaux dont varie l\u2019emplagement de certains sommets [PhD dissertation]. University of Montr\u00e9al Montr\u00e9al, Canada; 1978."},{"key":"pcbi.1009100.ref030","first-page":"1","volume-title":"Statistical decision theory and related topics","author":"J Neyman","year":"1971"},{"issue":"3","key":"pcbi.1009100.ref031","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/j.tcs.2008.06.046","article-title":"The Steiner tree problem on graphs: Inapproximability results","volume":"406","author":"M Chleb\u00edk","year":"2008","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"pcbi.1009100.ref032","doi-asserted-by":"crossref","first-page":"857","DOI":"10.1137\/S0097539795281086","article-title":"The k-Steiner ratio in graphs","volume":"26","author":"A Borchers","year":"1997","journal-title":"SIAM Journal on Computing"},{"key":"pcbi.1009100.ref033","article-title":"ProSolo: Accurate Variant Calling from Single Cell DNA Sequencing Data","author":"D L\u00e4hnemann","year":"2020","journal-title":"bioRxiv"},{"issue":"4260","key":"pcbi.1009100.ref034","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"},{"issue":"8","key":"pcbi.1009100.ref035","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1038\/nm0811-935","article-title":"miRNAs in the spotlight: understanding cancer gene dependency","volume":"17","author":"CM Croce","year":"2011","journal-title":"Nature Medicine"},{"issue":"3","key":"pcbi.1009100.ref036","doi-asserted-by":"crossref","first-page":"564","DOI":"10.1016\/j.cell.2017.06.010","article-title":"Defining a cancer dependency map","volume":"170","author":"A Tsherniak","year":"2017","journal-title":"Cell"},{"issue":"1","key":"pcbi.1009100.ref037","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1038\/s41467-019-13805-y","article-title":"Agreement between two large pan-cancer CRISPR-Cas9 gene dependency data sets","volume":"10","author":"JM Dempster","year":"2019","journal-title":"Nature communications"}],"updated-by":[{"DOI":"10.1371\/journal.pcbi.1009100","type":"new_version","label":"New version","source":"publisher","updated":{"date-parts":[[2022,8,30]],"date-time":"2022-08-30T00:00:00Z","timestamp":1661817600000}}],"container-title":["PLOS Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pcbi.1009100","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,30]],"date-time":"2022-08-30T14:44:35Z","timestamp":1661870675000},"score":1,"resource":{"primary":{"URL":"https:\/\/dx.plos.org\/10.1371\/journal.pcbi.1009100"}},"subtitle":[],"editor":[{"given":"Joshua","family":"Welch","sequence":"first","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2022,8,11]]},"references-count":37,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2022,8,11]]}},"URL":"https:\/\/doi.org\/10.1371\/journal.pcbi.1009100","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/2021.05.24.445405","asserted-by":"object"}]},"ISSN":["1553-7358"],"issn-type":[{"value":"1553-7358","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,11]]}}}