{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T08:59:42Z","timestamp":1769849982630,"version":"3.49.0"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031902512","type":"print"},{"value":"9783031902529","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-90252-9_8","type":"book-chapter","created":{"date-parts":[[2025,4,24]],"date-time":"2025-04-24T20:03:15Z","timestamp":1745524995000},"page":"118-133","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Dynamic Programming Algorithms for\u00a0Fast and\u00a0Accurate Cell Lineage Tree Reconstruction from\u00a0CRISPR-Based Lineage Tracing Data"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-5699-2196","authenticated-orcid":false,"given":"Junyan","family":"Dai","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5553-3312","authenticated-orcid":false,"given":"Erin K.","family":"Molloy","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,4,25]]},"reference":[{"issue":"7699","key":"8_CR1","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1038\/nature25969","volume":"556","author":"A Alemany","year":"2018","unstructured":"Alemany, A., Florescu, M., Baron, C.S., Peterson-Maduro, J., van Oudenaarden, A.: Whole-organism clone tracing using single-cell sequencing. Nature 556(7699), 108\u2013112 (2018)","journal-title":"Nature"},{"key":"8_CR2","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13015-017-0120-1","volume":"13","author":"MS Bayzid","year":"2018","unstructured":"Bayzid, M.S., Warnow, T.: Gene tree parsimony for incomplete gene trees: addressing true biological loss. Algorithms Mol. Biol. 13, 1 (2018)","journal-title":"Algorithms Mol. Biol."},{"key":"8_CR3","doi-asserted-by":"publisher","first-page":"311","DOI":"10.2307\/2406441","volume":"19","author":"JH Camin","year":"1965","unstructured":"Camin, J.H., Sokal, R.R.: A method for deducing branching sequences in phylogeny. Evolution 19, 311\u2013326 (1965)","journal-title":"Evolution"},{"key":"8_CR4","doi-asserted-by":"publisher","unstructured":"Dai, J., Molloy, E.K.: Dynamic programming algorithms for fast and accurate cell lineage tree reconstruction from CRISPR-based lineage tracing data. bioRxiv (2024). https:\/\/doi.org\/10.1101\/2024.11.15.623872","DOI":"10.1101\/2024.11.15.623872"},{"issue":"1","key":"8_CR5","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1186\/s13015-023-00249-9","volume":"19","author":"J Dai","year":"2024","unstructured":"Dai, J., Rubel, T., Han, Y., Molloy, E.K.: Dollo-CDP: a polynomial-time algorithm for the clade-constrained large Dollo parsimony problem. Algorithms Mol. Biol. 19(1), 2 (2024)","journal-title":"Algorithms Mol. Biol."},{"issue":"1","key":"8_CR6","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/0025-5564(86)90161-6","volume":"81","author":"WH Day","year":"1986","unstructured":"Day, W.H., Johnson, D.S., Sankoff, D.: The computational complexity of inferring rooted phylogenies by parsimony. Math. Biosci. 81(1), 33\u201342 (1986). https:\/\/doi.org\/10.1016\/0025-5564(86)90161-6","journal-title":"Math. Biosci."},{"issue":"5","key":"8_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, B.J.: Inferring parsimonious migration histories for metastatic cancers. Nat. Genet. 50(5), 718\u2013726 (2018)","journal-title":"Nat. Genet."},{"issue":"24","key":"8_CR8","doi-asserted-by":"publisher","first-page":"4604","DOI":"10.1016\/j.cell.2022.10.028","volume":"185","author":"W Fang","year":"2022","unstructured":"Fang, W., et al.: Quantitative fate mapping: a general framework for analyzing progenitor state dynamics via retrospective lineage barcoding. Cell 185(24), 4604-4620.e32 (2022)","journal-title":"Cell"},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"Gong, W., et al.: Benchmarked approaches for reconstruction of in vitro cell lineages and in silico models of C. elegans and M. musculus developmental trees. Cell Syst. 12(8), 810\u2013826.e4 (2021)","DOI":"10.1016\/j.cels.2021.05.008"},{"issue":"1","key":"8_CR10","doi-asserted-by":"publisher","first-page":"101156","DOI":"10.1016\/j.cels.2024.11.013","volume":"16","author":"M Hirsch","year":"2025","unstructured":"Hirsch, M., et al.: Stochastic modelling of single-cell gene expression adaptation reveals non-genomic contribution to evolution of tumor subclones. Cell Syst. 16(1), 101156 (2025)","journal-title":"Cell Syst."},{"issue":"1","key":"8_CR11","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1186\/s13059-020-02000-8","volume":"21","author":"MG Jones","year":"2020","unstructured":"Jones, M.G., et al.: Inference of single-cell phylogenies from lineage tracing data using Cassiopeia. Genome Biol. 21(1), 92 (2020)","journal-title":"Genome Biol."},{"key":"8_CR12","doi-asserted-by":"publisher","unstructured":"Kane, D., Tao, T.: A bound on partitioning clusters. Electr. J. Comb. (2017). https:\/\/doi.org\/10.37236\/6797","DOI":"10.37236\/6797"},{"issue":"1","key":"8_CR13","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/j.jgg.2023.05.011","volume":"51","author":"Z Li","year":"2024","unstructured":"Li, Z., et al.: Reconstructing cell lineage trees with genomic barcoding: approaches and applications. J. Genet. Genomics 51(1), 35\u201347 (2024)","journal-title":"J. Genet. Genomics"},{"key":"8_CR14","doi-asserted-by":"publisher","unstructured":"Mai, U., Chu, G., Raphael, B.J.: Maximum likelihood inference of time-scaled cell lineage trees with mixed-type missing data. bioRxiv (2024). https:\/\/doi.org\/10.1101\/2024.03.05.583638","DOI":"10.1101\/2024.03.05.583638"},{"issue":"4260","key":"8_CR15","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1126\/science.959840","volume":"194","author":"PC Nowell","year":"1976","unstructured":"Nowell, P.C.: The clonal evolution of tumor cell populations. Science 194(4260), 23\u201328 (1976)","journal-title":"Science"},{"issue":"11","key":"8_CR16","doi-asserted-by":"publisher","first-page":"2685","DOI":"10.1038\/s41596-018-0058-x","volume":"13","author":"B Raj","year":"2018","unstructured":"Raj, B., Gagnon, J.A., Schier, A.F.: Large-scale reconstruction of cell lineages using single-cell readout of transcriptomes and CRISPR-Cas9 barcodes by scGESTALT. Nat. Protoc. 13(11), 2685\u20132713 (2018)","journal-title":"Nat. Protoc."},{"issue":"5","key":"8_CR17","doi-asserted-by":"publisher","first-page":"442","DOI":"10.1038\/nbt.4103","volume":"36","author":"B Raj","year":"2018","unstructured":"Raj, B., et al.: Simultaneous single-cell profiling of lineages and cell types in the vertebrate brain. Nat. Biotechnol. 36(5), 442\u2013450 (2018)","journal-title":"Nat. Biotechnol."},{"issue":"1","key":"8_CR18","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0025-5564(81)90043-2","volume":"53","author":"D Robinson","year":"1981","unstructured":"Robinson, D., Foulds, L.: Comparison of phylogenetic trees. Math. Biosci. 53(1), 131\u2013147 (1981)","journal-title":"Math. Biosci."},{"key":"8_CR19","doi-asserted-by":"crossref","unstructured":"Salvador-Mart\u00ednez, I., Grillo, M., Averof, M., Telford, M.J.: Is it possible to reconstruct an accurate cell lineage using CRISPR recorders? eLife 8, e40292 (2019)","DOI":"10.7554\/eLife.40292"},{"issue":"6041","key":"8_CR20","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1126\/science.1206357","volume":"333","author":"MJ Sanderson","year":"2011","unstructured":"Sanderson, M.J., McMahon, M.M., Steel, M.: Terraces in phylogenetic tree space. Science 333(6041), 448\u2013450 (2011)","journal-title":"Science"},{"key":"8_CR21","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1007\/BF01681346","volume":"9","author":"D Sankoff","year":"1975","unstructured":"Sankoff, D., Rousseau, P.: Locating the vertices of a steiner tree in an arbitrary metric space. Math. Program. 9, 240\u2013246 (1975)","journal-title":"Math. Program."},{"key":"8_CR22","doi-asserted-by":"publisher","first-page":"1113","DOI":"10.1016\/j.cels.2023.11.005","volume":"14","author":"P Sashittal","year":"2023","unstructured":"Sashittal, P., Schmidt, H., Chan, M., Raphael, B.J.: Startle: a star homoplasy approach for CRISPR-Cas9 lineage tracing. Cell Syst. 14, 1113\u20131121 (2023)","journal-title":"Cell Syst."},{"key":"8_CR23","doi-asserted-by":"publisher","unstructured":"Sashittal, P., et al.: Inferring cell differentiation maps from lineage tracing data. bioRxiv (2024). https:\/\/doi.org\/10.1101\/2024.09.09.611835","DOI":"10.1101\/2024.09.09.611835"},{"issue":"5","key":"8_CR24","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1038\/nbt.4124","volume":"36","author":"B Spanjaard","year":"2018","unstructured":"Spanjaard, B., et al.: Simultaneous lineage tracing and cell-type identification using CRISPR-Cas9-induced genetic scars. Nat. Biotechnol. 36(5), 469\u2013473 (2018)","journal-title":"Nat. Biotechnol."},{"key":"8_CR25","unstructured":"Swofford, D.L.: PAUP*. Phylogenetic Analysis Using Parsimony (*and Other Methods). Version 4. Sinauer Associates, Sunderland, Massachusetts (2003)"},{"issue":"Suppl 5","key":"8_CR26","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1186\/s12864-018-4621-1","volume":"19","author":"P Vachaspati","year":"2018","unstructured":"Vachaspati, P., Warnow, T.: SIESTA: enhancing searches for optimal supertrees and species trees. BMC Genomics 19(Suppl 5), 252 (2018)","journal-title":"BMC Genomics"},{"key":"8_CR27","doi-asserted-by":"publisher","first-page":"778","DOI":"10.1038\/s41587-023-01887-5","volume":"42","author":"K Wang","year":"2024","unstructured":"Wang, K., et al.: Phylovelo enhances transcriptomic velocity field mapping using monotonically expressed genes. Nat. Biotechnol. 42, 778\u2013789 (2024)","journal-title":"Nat. Biotechnol."},{"key":"8_CR28","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 University Press, Cambridge (2017)"},{"issue":"11","key":"8_CR29","doi-asserted-by":"publisher","first-page":"1905","DOI":"10.1016\/j.cell.2022.04.015","volume":"185","author":"D Yang","year":"2022","unstructured":"Yang, D., et al.: Lineage tracing reveals the phylodynamics, plasticity, and paths of tumor evolution. Cell 185(11), 1905-1923.e25 (2022)","journal-title":"Cell"},{"issue":"6","key":"8_CR30","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1186\/s12859-018-2129-y","volume":"19","author":"C Zhang","year":"2018","unstructured":"Zhang, C., Rabiee, M., Sayyari, E., Mirarab, S.: ASTRAL-III: polynomial time species tree reconstruction from partially resolved gene trees. BMC Bioinf. 19(6), 153 (2018)","journal-title":"BMC Bioinf."}],"container-title":["Lecture Notes in Computer Science","Research in Computational Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-90252-9_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,24]],"date-time":"2025-04-24T20:03:17Z","timestamp":1745524997000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-90252-9_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031902512","9783031902529"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-90252-9_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"25 April 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"RECOMB","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Research in Computational Molecular Biology","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Seoul","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Korea (Republic of)","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 April 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 April 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"recomb2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/recomb.org\/recomb2025\/index.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}