Maximum Likelihood Inference of Time-Scaled Cell Lineage Trees with Mixed-Type Missing Data

Recent dynamic lineage tracing technologies combine CRISPR-based genome editing with single-cell sequencing to track cell divisions during development. A key problem in lineage tracing is to infer a cell lineage tree from the measured CRISPR-induced mutations. Several features of lineage tracing data distinguish this problem from standard phylogenetic tree inference: CRISPR-induced mutations are non-modifiable and can result in distinct sets of possible mutations at each target site; the number of mutations decreases over time due to non-modifiability; and CRISPR-based genome-editing and single-cell sequencing results in high rates of both heritable and non-heritable (dropout) missing data. To model these features, we introduce the Probabilistic Mixed-type Missing (PMM) model. We describe an algorithm, LAML (Lineage Analysis via Maximum Likelihood), to compute a maximum likelihood tree under the PMM model. LAML combines an Expectation Maximization (EM) algorithm with a heuristic tree search to jointly estimate tree topology, branch lengths and missing data parameters.