Estimation of cell lineage trees by maximum-likelihood phylogenetics

Jean Feng, William S. DeWitt, Aaron McKenna, Noah Simon, Amy D. Willis, F. A. MatsenbioRxiv 2019 · DOI

Abstract

CRISPR technology has enabled large-scale cell lineage tracing for complex multicellular organisms by mutating synthetic genomic barcodes during organismal development. However, these sophisticated biological tools currently use ad-hoc and outmoded computational methods to reconstruct the cell lineage tree from the mutated barcodes. Because these methods are agnostic to the biological mechanism, they are unable to take full advantage of the data’s structure. We propose a statistical model for the mutation process and develop a procedure to estimate the tree topology, branch lengths, and mutation parameters by iteratively applying penalized maximum likelihood estimation. In contrast to existing techniques, our method estimates time along each branch, rather than number of mutation events, thus providing a detailed account of tissue-type differentiation. Via simulations, we demonstrate that our method is substantially more accurate than existing approaches. Our reconstructed trees also better recapitulate known aspects of zebrafish development and reproduce similar results across fish replicates.

Introduction

Understanding how a single fertilized egg develops into a complex multicellular organism requires a "cell lineage tree"—a map of every cell division. Technologies like GESTALT use CRISPR/Cas9 to create "scars" (insertions or deletions, called indels) in synthetic DNA barcodes as an embryo grows. These scars are inherited, allowing researchers to trace a cell's ancestry through the resulting mutations.

CRISPR-based cell lineage tracing mechanism during development.

However, existing reconstruction methods like Camin-Sokal parsimony or neighbor-joining are "mechanism-agnostic." They treat DNA mutations as simple, independent, and reversible events. CRISPR mutations are none of these: Cas9 can delete multiple targets at once, the process is strictly irreversible, and sites are highly dependent. Furthermore, older methods only estimate the number of mutations, leaving researchers without data on the actual time between cell divisions.

Methods: The GAPML Framework

We introduce GAPML (GESTALT analysis using penalized Maximum Likelihood), a statistical framework designed to move away from ad-hoc heuristics toward a formal biological model. GAPML models barcode evolution as a continuous-time Markov chain where targets are "cut" at specific rates, followed by a stochastic repair process.

To handle the potentially infinite number of possible indel sequences, we utilize a mathematical property called "lumpability," grouping states based on which targets are still "active" (uncut). This makes likelihood calculations computationally tractable. Because the number of barcodes is often small relative to tree complexity, we apply a penalty to branch lengths and mutation parameters to prevent over-fitting.

Varying resolutions of cell lineage trees, including the use of caterpillar trees to resolve multifurcations.

A key innovation in GAPML is its approach to tree resolution. To resolve "multifurcations" (nodes where many branches seem to start at once), the model projects them onto "caterpillar trees." This allows the algorithm to estimate the specific order and timing of events, providing a higher-resolution view of development than traditional star-tree models.

Key Results

  • Superior Accuracy: In simulations, GAPML consistently outperformed existing methods across multiple metrics, including the BHV distance (a measure of tree similarity) and internal node height correlation.
  • High Replicability: When applied to real zebrafish data, GAPML showed a correlation of 0.770 between tissue distances across different fish replicates. In contrast, existing methods showed much lower or even negative correlations, suggesting they were capturing noise rather than biology.
  • Detailed Ontogeny: GAPML successfully identified that the zebrafish digestive tract is among the last to fully differentiate (around day four), matching established biological observations. It also recovered known developmental patterns, such as the early separation of the ectoderm, without being given any tissue-type information.

Discussion and Future Work

By incorporating the irreversibility and site-dependency of CRISPR, GAPML extracts significantly more information from lineage data than general-purpose phylogenetic tools. Estimating branch lengths in units of time allows researchers to compare parallel lineages and identify when specific tissues began to differentiate.

While GAPML is computationally more intensive than simpler methods, its accuracy and biological relevance represent a significant step forward. Future work will focus on integrating this lineage information with single-cell RNA sequencing data to provide a complete picture of how a cell's ancestry determines its eventual function, as well as refining uncertainty quantification for these complex reconstructions.

Summary updated

Abstract

Abstract CRISPR technology has enabled large-scale cell lineage tracing for complex multicellular organisms by mutating synthetic genomic barcodes during organismal development. However, these sophisticated biological tools currently use ad-hoc and outmoded computational methods to reconstruct the cell lineage tree from the mutated barcodes. Because these methods are agnostic to the biological mechanism, they are unable to take full advantage of the data’s structure. We propose a statistical model for the mutation process and develop a procedure to estimate the tree topology, branch lengths, and mutation parameters by iteratively applying penalized maximum likelihood estimation. In contrast to existing techniques, our method estimates time along each branch, rather than number of mutation events, thus providing a detailed account of tissue-type differentiation. Via simulations, we demonstrate that our method is substantially more accurate than existing approaches. Our reconstructed trees also better recapitulate known aspects of zebrafish development and reproduce similar results across fish replicates.
BibTeX
@misc{feng2019estimation,
  author = {Jean Feng and William S. DeWitt and Aaron McKenna and Noah Simon and Amy D. Willis and F. A. Matsen},
  title = {{Estimation of cell lineage trees by maximum-likelihood phylogenetics}},
  year = {2019},
  eprint = {1904.00117},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1904.00117},
  howpublished = {bioRxiv},
}
Figure