{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T06:48:56Z","timestamp":1772520536803,"version":"3.50.1"},"reference-count":19,"publisher":"Oxford University Press (OUP)","issue":"3","license":[{"start":{"date-parts":[[2019,8,28]],"date-time":"2019-08-28T00:00:00Z","timestamp":1566950400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/100000001","name":"US National Science Foundation","doi-asserted-by":"crossref","award":["IIS-1526415"],"award-info":[{"award-number":["IIS-1526415"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"US National Science Foundation","doi-asserted-by":"crossref","award":["CCF-1718093"],"award-info":[{"award-number":["CCF-1718093"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,2,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>Cells in an organism share a common evolutionary history, called cell lineage tree. Cell lineage tree can be inferred from single cell genotypes at genomic variation sites. Cell lineage tree inference from noisy single cell data is a challenging computational problem. Most existing methods for cell lineage tree inference assume uniform uncertainty in genotypes. A key missing aspect is that real single cell data usually has non-uniform uncertainty in individual genotypes. Moreover, existing methods are often sampling based and can be very slow for large data.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>In this article, we propose a new method called ScisTree, which infers cell lineage tree and calls genotypes from noisy single cell genotype data. Different from most existing approaches, ScisTree works with genotype probabilities of individual genotypes (which can be computed by existing single cell genotype callers). ScisTree assumes the infinite sites model. Given uncertain genotypes with individualized probabilities, ScisTree implements a fast heuristic for inferring cell lineage tree and calling the genotypes that allow the so-called perfect phylogeny and maximize the likelihood of the genotypes. Through simulation, we show that ScisTree performs well on the accuracy of inferred trees, and is much more efficient than existing methods. The efficiency of ScisTree enables new applications including imputation of the so-called doublets.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and implementation<\/jats:title>\n                    <jats:p>The program ScisTree is available for download at: https:\/\/github.com\/yufengwudcs\/ScisTree.<\/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\/btz676","type":"journal-article","created":{"date-parts":[[2019,8,27]],"date-time":"2019-08-27T07:37:44Z","timestamp":1566891464000},"page":"742-750","source":"Crossref","is-referenced-by-count":36,"title":["Accurate and efficient cell lineage tree inference from noisy single cell data: the maximum likelihood perfect phylogeny approach"],"prefix":"10.1093","volume":"36","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4988-3521","authenticated-orcid":false,"given":"Yufeng","family":"Wu","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, University of Connecticut , Storrs, CT 06269, USA"}]}],"member":"286","published-online":{"date-parts":[[2019,8,28]]},"reference":[{"key":"2023013110022767800_btz676-B1","doi-asserted-by":"crossref","first-page":"S53.","DOI":"10.1186\/1471-2105-12-S1-S53","article-title":"Linkage disequilibrium based genotype calling from low-coverage shotgun sequencing reads","volume":"12","author":"Duitama","year":"2011","journal-title":"BMC Bioinformatics"},{"key":"2023013110022767800_btz676-B2","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":"2023013110022767800_btz676-B3","doi-asserted-by":"crossref","first-page":"883","DOI":"10.1056\/NEJMoa1113205","article-title":"Intratumor heterogeneity and branched evolution revealed by multiregion sequencing","volume":"366","author":"Gerlinger","year":"2012","journal-title":"N. Engl. J. Med"},{"key":"2023013110022767800_btz676-B4","doi-asserted-by":"crossref","first-page":"353.","DOI":"10.1038\/nature14347","article-title":"The evolutionary history of lethal metastatic prostate cancer","volume":"520","author":"Gundem","year":"2015","journal-title":"Nature"},{"key":"2023013110022767800_btz676-B5","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1002\/net.3230210104","article-title":"Efficient algorithms for inferring evolutionary history","volume":"21","author":"Gusfield","year":"1991","journal-title":"Networks"},{"key":"2023013110022767800_btz676-B6","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology","author":"Gusfield","year":"1997"},{"key":"2023013110022767800_btz676-B7","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/9432.001.0001","volume-title":"ReCombinatorics: The Algorithmics of Ancestral Recombination Graphs and Explicit Phylogenetic Networks","author":"Gusfield","year":"2014"},{"key":"2023013110022767800_btz676-B8","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":"2023013110022767800_btz676-B9","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":"2023013110022767800_btz676-B10","doi-asserted-by":"crossref","first-page":"i917","DOI":"10.1093\/bioinformatics\/bty571","article-title":"Computational enhancement of single-cell sequences for inferring tumor evolution","volume":"17","author":"Miura","year":"2018","journal-title":"Bioinformatics"},{"key":"2023013110022767800_btz676-B11","doi-asserted-by":"crossref","first-page":"555.","DOI":"10.1038\/nmeth.3903","article-title":"Genotyping tumor clones from single-cell data","volume":"13","author":"Navin","year":"2016","journal-title":"Nat. Methods"},{"key":"2023013110022767800_btz676-B12","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":"2023013110022767800_btz676-B13","first-page":"406","article-title":"The neighbor-joining method: a new method for reconstructing phylogenetic trees","volume":"4","author":"Saitou","year":"1987","journal-title":"Mol. Biol. Evol"},{"key":"2023013110022767800_btz676-B14","doi-asserted-by":"crossref","first-page":"618.","DOI":"10.1038\/nrg3542","article-title":"Single-cell sequencing-based technologies will revolutionize whole-organism science","volume":"14","author":"Shapiro","year":"2013","journal-title":"Nat. Rev. Genet"},{"key":"2023013110022767800_btz676-B15","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":"2023013110022767800_btz676-B16","doi-asserted-by":"crossref","first-page":"2857.","DOI":"10.1038\/onc.2016.438","article-title":"Evolution and heterogeneity of non-hereditary colorectal cancer revealed by single-cell exome sequencing","volume":"36","author":"Wu","year":"2017","journal-title":"Oncogene"},{"key":"2023013110022767800_btz676-B17","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":"2023013110022767800_btz676-B18","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":"2023013110022767800_btz676-B19","doi-asserted-by":"crossref","first-page":"1622","DOI":"10.1126\/science.1229164","article-title":"Genome-wide detection of single-nucleotide and copy-number variations of a single human cell","volume":"338","author":"Zong","year":"2012","journal-title":"Science"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btz676\/30040801\/btz676.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/36\/3\/742\/48982048\/bioinformatics_36_3_742.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/36\/3\/742\/48982048\/bioinformatics_36_3_742.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T13:50:47Z","timestamp":1675173047000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/36\/3\/742\/5555811"}},"subtitle":[],"editor":[{"given":"Russell","family":"Schwartz","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2019,8,28]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,2,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btz676","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/742395","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":[[2020,2,1]]},"published":{"date-parts":[[2019,8,28]]}}}