Dynamic Programming for Scalable Cell Lineage Tree Reconstruction with Interpretable Optimality Guarantees

Explore dynamic programming algorithms for reconstructing cell lineage trees from CRISPR-based lineage tracing data in this 25-minute conference talk. Learn about scalable computational methods that provide interpretable optimality guarantees for cell lineage tree reconstruction, addressing key challenges in analyzing cellular development and evolution. Discover polynomial-time algorithms for the clade-constrained large Dollo parsimony problem and understand how quartet-based approaches enable statistically consistent estimation under unbiased error and missingness models. Examine partition function algorithms for evaluating inferred subclonal structures in single-cell sequencing data and gain insights into the mathematical foundations that make these reconstruction methods both accurate and computationally efficient. Understand the practical applications of these algorithms in developmental biology and cancer research, where accurate lineage tracing is crucial for understanding cellular processes and disease progression.