ConvexML: Fast and Accurate Branch Length Estimation under Irreversible Mutation Models, Illustrated through Applications to CRISPR/Cas9-Based Lineage Tracing.

Branch length estimation is a fundamental problem in statistical phylogenetics and a core component of tree reconstruction algorithms. Traditionally, general time-reversible mutation models are employed, and many software tools exist for this scenario. With the advent of CRISPR/Cas9 lineage tracing technologies, there has been significant interest in the study of branch length estimation under irreversible mutation models. Under the CRISPR/Cas9 mutation model, irreversible mutations-in the form of DNA insertions or deletions-are accrued during the experiment, which are then read out at the single-cell level to reconstruct the cell lineage tree. However, most of the analyses of CRISPR/Cas9 lineage tracing data have so far been limited to the reconstruction of single-cell tree topologies, which depict lineage relationships between cells, but not the amount of time that has passed between ancestral cell states and the present. Time-resolved trees, known as chronograms, would allow one to study the evolutionary dynamics of cell populations at an unprecedented level of resolution. Indeed, time-resolved trees would reveal the timing of events on the tree, the relative fitness of subclones, and the dynamics underlying phenotypic changes in the cell population-among other important applications. In this work, we introduce the first scalable and accurate method to refine any given single-cell tree topology into a single-cell chronogram by estimating its branch lengths. To do this, we perform regularized maximum likelihood estimation (MLE) under a general irreversible mutation model, paired with a conservative version of maximum parsimony that reconstructs only the ancestral states that we are confident about. To deal with the particularities of CRISPR/Cas9 lineage tracing data-such as double-resection events, which affect runs of consecutive sites-we avoid making our model more complex and instead opt for using a simple but effective data encoding scheme. Similarly, we avoid explicitly modeling the missing data mechanisms-such as heritable missing data-by instead assuming that they are missing completely at random. We stabilize estimates in low-information regimes by using a simple penalized version of MLE using a minimum branch length constraint and pseudocounts. All this leads to a convex MLE problem that can be readily solved in seconds with off-the-shelf convex optimization solvers. We benchmark our method using both simulations and real lineage tracing data, and show that it performs well on several tasks, matching or outperforming competing methods such as TiDeTree and LAML (Lineage Analysis via Maximum Likelihood) in terms of accuracy, while being $10\sim 100\times$ faster. Notably, our statistical model is simpler and more general, as we do not explicitly model the intricacies of CRISPR/Cas9 lineage tracing data. In this sense, our contribution is 2-fold: (1) a fast and robust method for branch length estimation under a general irreversible mutation model and (2) a data encoding scheme specific to CRISPR/Cas9 lineage tracing data, which makes it amenable to the general model. Our branch length estimation method, which we call "ConvexML," should be broadly applicable to any evolutionary model with irreversible mutations (ideally, with high diversity) and an approximately ignorable missing data mechanism. "ConvexML" is available through the convexml open-source Python package.