Dept. of Computer Science

Reconstructing Maximum Likelihood Time-resolved Cell Lineage Trees On Lineage Tracing Data

Studies of tissue development and disease have greatly benefited from recent advances in genome editing and single-cell sequencing. These recent advances are loosely referred to as dynamic lineage tracing systems. Given such data, a key analysis task is to infer a cell lineage tree, whose topology describes the cell division history and whose branch lengths indicate time between ancestral cell divisions (i.e. “time-resolved branch lengths”). We present Lineage Analysis via Maximum Likelihood (LAML), an efficient algorithm to infer a maximum likelihood time-resolved cell lineage tree under the Probabilistic Mixed-type Missing (PMM) evolutionary model. The PMM model distills key features of CRISPR-based dynamic lineage tracers: non-modifiability of edits; missing data due to both heritable transcriptomic silencing and dropout during single-cell RNA sequencing; and decreasing number of edits over time. On simulated data and mouse developmental models, LAML infers more accurate tree topologies and branch lengths, showing higher concordance with gene expression and developmental processes compared to existing methods.