Integrative Inference of Spatially Resolved Cell Lineage Trees using LineageMap

This paper introduces LineageMap, a novel hybrid probabilistic algorithm that integrates spatial locations, gene expression profiles, and lineage barcodes from single-cell data to accurately reconstruct high-resolution cell lineage trees and infer ancestral cell states and locations, outperforming existing methods in both simulated and experimental datasets.

The Gist

Imagine you are trying to solve a massive, three-dimensional jigsaw puzzle, but the pieces are invisible, the picture keeps changing, and some pieces are missing entirely.

This is essentially what biologists face when they try to understand how a single fertilized egg grows into a complex human body with billions of cells. They need to figure out the family tree of every cell (who is the parent, who is the child) and where that family lived and moved as it grew.

This paper introduces a new computer program called LineageMap that acts like a super-smart detective to solve this puzzle. Here is how it works, broken down into simple concepts:

1. The Three Clues (The "Tri-Modality" Data)

In the past, scientists had to guess the family tree using just one clue: a genetic "barcode" (like a unique tattoo on every cell). But tattoos can fade, get smudged, or look identical on different people (a problem called homoplasy).

Now, thanks to new technology, scientists have three clues for every single cell:

• The Barcode: The genetic tattoo (tells us who is related to whom).
• The Transcriptome: The cell's "ID card" or "job description" (tells us what type of cell it is, like a skin cell or a nerve cell).
• The Location: The cell's GPS coordinates (tells us exactly where it is sitting in the tissue).

The Problem: Existing computer programs were like detectives who only looked at the tattoos. They often got confused when the tattoos were smudged or when two unrelated people happened to have similar tattoos. They ignored the fact that family members usually live near each other and have similar jobs.

2. The Solution: LineageMap (The "Smart Detective")

LineageMap is a new algorithm that looks at all three clues at once. It uses a clever two-step strategy to solve the puzzle efficiently:

Step A: The "Group Hug" (Clustering)

First, the program looks at the genetic barcodes and groups cells that look very similar together. Imagine a teacher asking students to sit at tables with their cousins.

• Instead of trying to figure out the exact order of birth for 1,000 kids at once (which is a nightmare), LineageMap first groups them into 10 families.
• It builds a rough "backbone" tree showing how these 10 families are related. This is fast and prevents the computer from getting overwhelmed.

Step B: The "Fine-Tuning" (Likelihood Optimization)

Once the families are grouped, LineageMap zooms in on each family. It uses a sophisticated mathematical model (a "likelihood engine") to ask:

• "Given that these cells are genetically related, live in this specific neighborhood, and have these specific jobs, what is the most likely order in which they were born?"

It treats the tissue like a flowing river. If a cell moves from the "skin" area to the "muscle" area, the program understands that this movement is part of the family's history. It combines the genetic data with the spatial movement to fill in the missing pieces of the puzzle.

3. Why It's Better (The "Magic" Analogy)

Think of trying to reconstruct a family tree using only old, faded photos (the barcodes).

• Old Methods: They might guess that two strangers are brothers because they both have a scar on their left cheek (a coincidence).
• LineageMap: It looks at the photos, but it also checks their addresses and their jobs. It realizes, "Wait, these two live in different cities and have totally different careers. They probably aren't brothers, even if they have similar scars."

Because it uses all the information, LineageMap is much better at:

• Handling Missing Data: If a barcode is smudged (missing data), it uses the location and job description to guess the connection.
• Solving "Polytomies": Sometimes, many cells look identical (like a big family of twins). LineageMap uses their spatial positions to figure out who is the oldest twin and who is the youngest.

4. The Results

The authors tested LineageMap on:

1. Fake Data: They created a computer simulation of cells growing and moving. LineageMap solved the family tree much more accurately than any other method, especially when the data was "noisy" or incomplete.
2. Real Data: They used it on mouse embryonic stem cells. It successfully reconstructed how the cells grew from a single point, moved to the edges, and turned into different types of cells, matching what biologists expected to see.

The Bottom Line

LineageMap is a powerful new tool that helps scientists see the "movie" of life, not just a still photo. By combining genetics, location, and cell type, it can draw a highly accurate map of how tissues grow, heal, and sometimes go wrong (like in cancer). It turns a messy, confusing pile of data into a clear, understandable story of life's journey.

Technical Summary

1. Problem Statement

The paper addresses the challenge of reconstructing spatially resolved cell lineage trees from emerging tri-modality single-cell datasets. These datasets contain three distinct data types for each cell:

1. Lineage Barcodes: Heritable molecular marks (e.g., CRISPR-induced mutations) recording cell division history.
2. Gene Expression Profiles: Transcriptomic data indicating cell state and differentiation.
3. Spatial Coordinates: Physical locations of cells within a tissue.

Key Challenges:

• Computational Intractability: Traditional Maximum Likelihood (ML) or Bayesian methods for tree inference are computationally prohibitive for thousands of cells due to the combinatorial explosion of possible tree topologies ($n!!$).
• Data Noise: Lineage barcode data suffers from high dropout rates (missing mutations) and homoplasy (identical mutations arising independently), leading to ambiguous relationships.
• Polytomy: Many cells share identical barcodes, creating unresolved "star" nodes (polytomies) in the tree that standard methods cannot easily resolve.
• Lack of Integration: Existing methods typically use only barcodes or barcodes + expression, failing to leverage the mutual constraints between lineage, spatial proximity, and cell state continuity.

2. Methodology: LineageMap

LineageMap is a hybrid, hierarchical framework that combines the scalability of distance-based methods with the accuracy of likelihood-based optimization under a unified probabilistic model.

A. Two-Stage Inference Pipeline

1. Global Backbone Construction (Distance-Based):

   • Clustering: Cells are aggregated into "clones" (groups with highly similar barcodes) using Louvain clustering on a similarity graph derived from a dropout-aware weighted Hamming distance.
   • Consensus: A consensus barcode is generated for each cluster.
   • Cluster-Constrained Neighbor Joining (NJ): A standard NJ algorithm is adapted to build a "backbone tree" of these clusters, ensuring that cells within the same clone form a subtree. This reduces the search space and handles early barcode noise.

2. Local Refinement (Likelihood-Based):

   • Within each cluster, a Maximum Likelihood (ML) framework is applied to refine the local tree topology and branch lengths.
   • Local Search: The algorithm uses a stochastic Random Subtree Swapping (rSS) strategy (a derivative of SPR) with a "first-improvement" heuristic to escape local optima efficiently without exhaustive search.
   • Merging: Optimized subtrees are re-attached to the global backbone.

B. Unified Probabilistic Model

LineageMap defines a joint likelihood function $L(T, \theta)$ that couples three generative models:

1. Barcode Evolution Model: An irreversible continuous-time Markov chain (CTMC) modeling CRISPR-Cas9 mutations. It accounts for dropout events and the irreversibility of edits (Camin-Sokal parsimony logic).
2. Spatial Evolution Model: Models cell migration as a diffusion process.
   • Brownian Motion: Basic model where daughter cell location depends on the parent's location plus a drift field and diffusion noise.
   • Ornstein-Uhlenbeck (OU) Extension: Allows for state-dependent migration toward specific "attractor" locations (e.g., specific tissue regions), modeling directed migration based on cell state.
3. Cell State Evolution Model: Models discrete cell states (e.g., cell types) evolving via a CTMC along the tree, potentially drifting toward lineage-specific attractors.

The joint likelihood factorizes into terms for barcodes, spatial coordinates, and cell states, allowing the algorithm to infer ancestral locations and states simultaneously.

3. Key Contributions

• Algorithmic Innovation: Introduction of LineageMap, the first method to jointly infer lineage trees, ancestral spatial locations, and ancestral states using a hybrid distance-likelihood approach.
• Handling Polytomy: Solves the "polytomy problem" by using transcriptomic and spatial similarity to distinguish cells with identical barcodes, refining local tree structures.
• Scalability: The two-stage design (Backbone + Local Refinement) makes ML inference feasible for datasets with thousands of cells, overcoming the $O(n!)$ complexity barrier of global ML search.
• Simulation Tool: Development of SpaTedSim, a simulator that generates realistic ground-truth tri-modality data (barcodes, expression, spatial) to benchmark lineage reconstruction methods.

4. Results

The authors evaluated LineageMap on both synthetic data (generated by SpaTedSim) and experimental data (baseMEMOIR mouse embryonic stem cells).

Synthetic Data Benchmarks:

• Metrics: Compared against LinRace, Cassiopeia, Startle, and NJ using Robinson-Foulds (RF) distance, Nye similarity, and path-length correlation.
• Performance: LineageMap consistently outperformed all state-of-the-art methods across varying conditions (cell counts, target sites, and dropout rates).
• Robustness: It demonstrated superior stability in high-difficulty scenarios:
  • High Dropout (80%): Maintained high accuracy where other methods collapsed.
  • Sparse Mutations (16 target sites): Successfully recovered topological structure where signal was weak.
  • Small Datasets: Maintained leading performance even with reduced cell counts.

Experimental Data (baseMEMOIR mESC):

• Applied to mouse embryonic stem cell (mESC) colonies.
• Spatial Coherence: The inferred trees preserved spatial clustering (e.g., naive cells in the center, formative cells at the boundary), which was not captured by barcode-only methods.
• Accuracy: LineageMap showed the highest agreement with the reference phylogeny reported in the original baseMEMOIR study across all similarity metrics (lowest RF distance, highest Nye similarity).

5. Significance

• Bridging Modalities: LineageMap effectively bridges molecular lineage tracing with spatial and transcriptomic information, moving beyond simple tree reconstruction to dynamic cellular ancestry reconstruction in both time and space.
• Biological Insight: By inferring ancestral locations, the method reveals how cell divisions and migrations coordinate to form tissue architecture, offering new insights into development, regeneration, and disease progression.
• Future-Proofing: As spatially resolved lineage tracing technologies mature and generate larger datasets, LineageMap provides a scalable, statistically principled framework essential for high-resolution analysis of tissue dynamics.

Availability: The code and simulator are open-source at https://github.com/ZhangLabGT/LineageMap and https://github.com/ZhangLabGT/SpaTedSim.