StarCDP: Dynamic Programming Algorithms for Fast and Accurate Cell Lineage Tree Reconstruction from CRISPR-Based Lineage Tracing Data

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's 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's strict consensus achieved the lowest SHP score and comparable numbers of metastatic reseedings compared to PAUP*'s 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: https://github.com/molloy-lab/Star-CDP.