{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T14:37:27Z","timestamp":1774535847302,"version":"3.50.1"},"reference-count":38,"publisher":"SAGE Publications","issue":"1","license":[{"start":{"date-parts":[[2025,10,29]],"date-time":"2025-10-29T00:00:00Z","timestamp":1761696000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Journal of Computational Biology"],"published-print":{"date-parts":[[2026,1]]},"abstract":"<jats:p>\n                    CRISPR-based lineage tracing, coupled with single-cell RNA sequencing, has emerged as a promising approach for studying development and disease progression at the cellular level. Thus, cell lineage tree (CLT) reconstruction has attracted significant attention in recent years, including the introduction of Star Homoplasy Parsimony (SHP) to model the unique properties of CRISPR-induced mutations, along with the Startle family of methods. However, CLT reconstruction continues to be challenged by technological limitations in producing consistent phylogenetic signals across CLTs. To address these issues, we present Star-CDP, a collection of dynamic programming algorithms that enable researchers to seek, count, sample, and build consensus trees from solutions to SHP within a constrained search space, defined by subsets of cells from which a solution must draw its clades. When using our procedure to construct clade constraints, Star-CDP runs in polynomial time, enabling scalability to larger numbers of cells than Startle-ILP (integer linear programming), the leading method for SHP. In simulations, Star-CDP\u2019s strict consensus achieved the same or higher accuracy (f1-score) compared to the leading parsimony methods, with the greatest gains in accuracy occurring when the phylogenetic signal was limited due to the high ratio of cells to mutations. On lineage tracing data from a mouse model of lung adenocarcinoma, Star-CDP\u2019s strict consensus achieved the lowest SHP score and comparable numbers of metastatic reseedings compared to PAUP*\u2019s strict consensus and Startle-NNI (nearest neighbor interchange), all benchmarked on a standard data processing pipeline (although our study also revealed that the pipeline can impact relative performance for migrations\/reseedings). Star-CDP is available on GitHub:\n                    <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"uri\" xlink:href=\"https:\/\/github.com\/molloy-lab\/Star-CDP\">https:\/\/github.com\/molloy-lab\/Star-CDP<\/jats:ext-link>\n                    .\n                  <\/jats:p>","DOI":"10.1177\/15578666251386082","type":"journal-article","created":{"date-parts":[[2025,10,29]],"date-time":"2025-10-29T10:31:52Z","timestamp":1761733912000},"page":"48-66","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":1,"title":["StarCDP: Dynamic Programming Algorithms for Fast and Accurate Cell Lineage Tree Reconstruction from CRISPR-Based Lineage Tracing Data"],"prefix":"10.1177","volume":"33","author":[{"given":"Junyan","family":"Dai","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Maryland, College Park, Maryland, USA."},{"name":"University of Maryland Institute for Advanced Computer Studies, University of Maryland, College Park, Maryland, USA."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Erin K.","family":"Molloy","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Maryland, College Park, Maryland, USA."},{"name":"University of Maryland Institute for Advanced Computer Studies, University of Maryland, College Park, Maryland, USA."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2025,10,29]]},"reference":[{"key":"e_1_3_3_2_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature25969"},{"key":"e_1_3_3_3_1","doi-asserted-by":"publisher","DOI":"10.1186\/s13015-017-0120-1"},{"issue":"3","key":"e_1_3_3_4_1","first-page":"311","article-title":"A method for deducing branching sequences in phylogeny","volume":"19","author":"Camin JH","year":"1965","unstructured":"Camin JH, , Sokal RR. A method for deducing branching sequences in phylogeny. Evolution (N Y), 1965; 19(3):311\u2013326.","journal-title":"Evolution (N Y)"},{"key":"e_1_3_3_5_1","doi-asserted-by":"publisher","DOI":"10.1186\/s13059-025-03649-9"},{"key":"e_1_3_3_6_1","doi-asserted-by":"publisher","DOI":"10.1186\/s13015-023-00249-9"},{"key":"e_1_3_3_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-90252-9_8"},{"key":"e_1_3_3_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0025-5564(86)90161-6"},{"key":"e_1_3_3_9_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41588-018-0106-z"},{"key":"e_1_3_3_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cell.2022.10.028"},{"key":"e_1_3_3_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cels.2021.05.008"},{"key":"e_1_3_3_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/332306.332359"},{"key":"e_1_3_3_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cels.2024.11.013"},{"key":"e_1_3_3_14_1","doi-asserted-by":"publisher","DOI":"10.1186\/s13059-020-02000-8"},{"key":"e_1_3_3_15_1","doi-asserted-by":"publisher","DOI":"10.37236\/6797"},{"key":"e_1_3_3_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jgg.2023.05.011"},{"key":"e_1_3_3_17_1","doi-asserted-by":"publisher","DOI":"10.1242\/dev.169730"},{"key":"e_1_3_3_18_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btv234"},{"key":"e_1_3_3_19_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btu462"},{"key":"e_1_3_3_20_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btaa444"},{"key":"e_1_3_3_21_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.959840"},{"key":"e_1_3_3_22_1","doi-asserted-by":"publisher","DOI":"10.1101\/2021.05.28.446021"},{"key":"e_1_3_3_23_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41596-018-0058-x"},{"key":"e_1_3_3_24_1","doi-asserted-by":"publisher","DOI":"10.1038\/nbt.4103"},{"key":"e_1_3_3_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0025-5564(81)90043-2"},{"key":"e_1_3_3_26_1","doi-asserted-by":"publisher","DOI":"10.7554\/eLife.40292"},{"key":"e_1_3_3_27_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.1206357"},{"key":"e_1_3_3_28_1","doi-asserted-by":"publisher","DOI":"10.1093\/sysbio\/syv024"},{"key":"e_1_3_3_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01681346"},{"key":"e_1_3_3_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cels.2023.11.005"},{"key":"e_1_3_3_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-90252-9_29"},{"key":"e_1_3_3_32_1","doi-asserted-by":"publisher","DOI":"10.1038\/nbt.4124"},{"key":"e_1_3_3_33_1","volume-title":"PAUP. Phylogenetic Analysis Using Parsimony (*and Other Methods)","author":"Swofford DL","year":"2003","unstructured":"Swofford DL. PAUP. Phylogenetic Analysis Using Parsimony (*and Other Methods). Sinauer Associates: Sunderland, MA; 2003."},{"key":"e_1_3_3_34_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btw600"},{"key":"e_1_3_3_35_1","doi-asserted-by":"publisher","DOI":"10.1186\/s12864-018-4621-1"},{"key":"e_1_3_3_36_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41587-023-01887-5"},{"key":"e_1_3_3_37_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781316882313"},{"key":"e_1_3_3_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cell.2022.04.015"},{"key":"e_1_3_3_39_1","doi-asserted-by":"publisher","DOI":"10.1186\/s12859-018-2129-y"}],"container-title":["Journal of Computational Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/15578666251386082","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/15578666251386082","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/15578666251386082","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,9]],"date-time":"2026-02-09T05:47:01Z","timestamp":1770616021000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.1177\/15578666251386082"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,29]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,1]]}},"alternative-id":["10.1177\/15578666251386082"],"URL":"https:\/\/doi.org\/10.1177\/15578666251386082","relation":{},"ISSN":["1066-5277","1557-8666"],"issn-type":[{"value":"1066-5277","type":"print"},{"value":"1557-8666","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,10,29]]}}}