VeloTree: Inferring single-cell trajectories from RNA velocity fields with varifold distances

The paper introduces VeloTree, a novel method that infers single-cell differentiation trees by calculating a robust path distance based on the squared varifold distance between RNA velocity integral curves, demonstrating high accuracy on both simulated and real datasets.

The Gist

Imagine you have a massive, chaotic photo album of a city's population. You have pictures of thousands of people, but you don't know who they are, where they came from, or how they are related. You just have a snapshot of everyone at one specific moment.

Now, imagine you want to figure out the family tree of this city: Who is the ancestor? Who are the parents? Who are the children? And how did the family grow and split over time?

This is exactly the problem scientists face with single-cell RNA sequencing. They have a snapshot of thousands of individual cells, but they don't know the "story" of how those cells developed from a single stem cell into a complex organism.

The paper you shared, VeloTree, introduces a new, clever way to solve this puzzle. Here is the breakdown in simple terms:

1. The Problem: A Static Snapshot vs. A Moving Movie

Usually, scientists look at cells like a still photograph. They see what genes are "on" or "off" right now. But cells are dynamic; they are constantly changing, like actors in a movie.

Recently, scientists discovered a trick called RNA Velocity. Think of this as a windsock or an arrow attached to every cell.

• Gene Expression: Tells you where the cell is right now (its location).
• RNA Velocity: Tells you which way the cell is moving and how fast (its direction and speed).

So, instead of just a dot on a map, every cell now has a little arrow pointing toward its future.

2. The Old Way: Connecting the Dots (and failing)

Previous methods tried to draw the family tree by simply connecting the closest dots (cells) together.

• The Flaw: If you have a noisy crowd, connecting the nearest people can create a messy, tangled web. It's like trying to draw a family tree by just asking, "Who is standing next to you?" You might connect two strangers who happen to be standing close, or miss a parent who is standing a few feet away. These methods are very sensitive to "noise" (errors in the data).

3. The New Way: VeloTree (The "River" Analogy)

The authors of VeloTree say: "Let's not just look at where the cells are standing. Let's look at the river they are flowing in."

Here is how their method works, step-by-step:

Step A: Cleaning the Wind (Preprocessing)

The "arrows" (velocity) in the data are often shaky and jittery, like wind gusts on a stormy day.

• The Fix: They smooth out the wind. They average the arrows of nearby cells to get a clear, steady flow direction. They also make sure the arrows point along the "road" (the shape of the data) rather than randomly off into the void.

Step B: Tracing the Path Backwards (Integration)

This is the magic part.

• Imagine you are standing on a riverbank. You see a leaf floating by.
• Instead of just looking at the leaf, you ask: "If I swim backwards against the current, where did this leaf come from?"
• VeloTree does this for every single cell. It traces a "virtual path" backwards from the cell's current position, following the arrows all the way back to the "source" (the root of the tree).
• Now, instead of just a dot, every cell has a string (a curve) attached to it, stretching all the way back to the beginning.

Step C: Measuring the Strings (Varifold Distance)

Now, how do we decide which cells are related?

• Old Method: "Are these two dots close together?"
• VeloTree Method: "Do these two strings look similar?"
• They use a mathematical tool called Varifold Distance. Think of this as a "shape matcher." It compares the two strings.
  • If two cells are siblings (children of the same parent), their strings will travel together for a long time before splitting. They will look very similar.
  • If two cells are unrelated, their strings will look very different.
  • Crucially, this method is robust. Even if the strings wiggle a bit (due to noise), the matcher knows they are still the same path.

Step D: Building the Tree

Once they have measured how similar every pair of strings is, they use a standard algorithm (called "Family Joining") to build the tree. It's like a puzzle solver that says, "These two strings are 99% identical, so they must be siblings. These two are 50% identical, so they are cousins."

Why is this a big deal?

1. It's Smarter: It doesn't just look at neighbors; it looks at the history and future of the cell.
2. It Handles Noise: Real biological data is messy. Because they compare the whole "string" (the path) rather than just a single point, small errors don't break the whole tree.
3. It Works on Real Data: They tested this on simulated data (computer models) and real mouse pancreas cells. In the mouse pancreas, they successfully figured out how stem cells turn into different types of hormone-producing cells, even identifying that some cells have a "dual origin" (a complex family history).

The Bottom Line

VeloTree is like upgrading from a static map to a GPS navigation system.

• Old methods just looked at where cars were parked.
• VeloTree looks at the traffic flow, traces the route every car took to get there, and uses those routes to reconstruct the entire highway system (the family tree) with high accuracy.

This allows scientists to finally see the "movie" of life unfolding, rather than just a single, confusing frame.

Technical Summary

1. Problem Statement

Trajectory Inference (TI) in single-cell transcriptomics aims to reconstruct the dynamic biological processes (e.g., differentiation) underlying a population of cells from static sequencing data.

• The Challenge: Standard TI methods often rely on constructing a Minimum Spanning Tree (MST) from a k-nearest neighbor graph based on cell similarity. These approaches are highly sensitive to noise and often fail to capture fine-grained differentiation structures.
• The Data: Modern single-cell RNA sequencing (scRNA-seq) provides not only gene expression levels but also RNA velocity (a vector indicating the direction and rate of gene expression change). This transforms the data into a discrete vector field.
• The Gap: Existing methods utilizing RNA velocity (e.g., VeTra, CellPath) often use dissimilarity measures based on temporal inconsistency or Euclidean distances in expression-velocity space. The authors argue that Euclidean distances fail to capture the hyperbolic nature of path distances on a tree, leading to suboptimal tree reconstruction.

2. Methodology: The VeloTree Pipeline

The authors propose a distance-based tree inference approach. Instead of building a graph and finding an MST, they define a robust dissimilarity measure between cells and use a tree reconstruction algorithm (Family-Joining) to infer the topology.

The pipeline consists of four main steps:

Step 1: Preprocessing and Denoising

RNA velocity estimates are noisy due to technical variability and kinetic assumptions.

• Smoothing: The velocity field is smoothed using a heat kernel construction derived from diffusion maps. This integrates local geometry without assuming uniform sample distribution.
• Tangent Projection: Velocities are projected onto the local tangent spaces of the cell point cloud. The local dimension is estimated by finding the radius that minimizes the average local dimension (targeting 1D trajectories), ensuring velocities align with the manifold of the data.

Step 2: Backward Integration

Instead of treating cells as static points, the method treats them as endpoints of trajectories.

• The smoothed velocity field is integrated backward in time from each cell $x_i$.
• This generates an integral curve $\gamma_i$ representing the hypothetical path the cell took from a root state to its current state.
• The integration uses a kernel regression to create a smooth vector field, with specific parameters for step size and integration margin to ensure convergence.

Step 3: Dissimilarity Calculation via Varifold Distance

This is the core theoretical contribution. The dissimilarity between two cells is defined as the squared varifold distance between their integral curves.

• Varifold Representation: Curves are represented as distributions over positions and oriented tangent vectors (oriented varifolds) embedded in a Reproducing Kernel Hilbert Space (RKHS).
• The Metric: The distance $d_{W^*}(\gamma_i, \gamma_j)$ measures the difference between these distributions. It is parameterized by:
  • $\sigma_x$: Spatial sensitivity (proximity of points).
  • $\sigma_t$: Angular sensitivity (proximity of tangent vectors).
• Rationale: This metric is robust to small deformations, invariant to reparameterization, and, crucially, maximizes the separation between divergent curves, making it topologically equivalent to the path distance on the underlying differentiation tree.

Step 4: Tree Inference

• The dissimilarity matrix $\Delta_{ij} = d_{W^*}(\gamma_i, \gamma_j)^2$ is fed into the Family-Joining algorithm.
• Unlike Neighbor-Joining (which assumes leaves are observed), Family-Joining handles observations at internal nodes (intermediate differentiation stages). It iteratively groups observations into sibling or parent-child relationships based on the additive property of tree distances.

3. Key Contributions

1. Novel Dissimilarity Measure: Introduction of the squared varifold distance between RNA velocity integral curves as a metric for cell dissimilarity. This bridges shape analysis (varifolds) with single-cell biology.
2. Theoretical Guarantees: The authors prove that under specific assumptions (smooth embedding, increasing distance/angle between branches), the varifold distance asymptotically approximates the shortest-path distance on the true differentiation tree. They show the dissimilarity matrix satisfies the four-point condition required for tree reconstruction.
3. Robust Preprocessing: A comprehensive routine for denoising RNA velocity fields via diffusion smoothing and tangent projection, addressing the high noise levels inherent in scRNA-seq data.
4. End-to-End Framework: A complete pipeline from raw velocity data to a reconstructed differentiation tree, implemented and tested on both synthetic and real data.

4. Results

The method was evaluated on simulated datasets (using the dyngen library) and a real dataset (mouse pancreatic endocrine cells).

• Simulated Data:

  • Accuracy: VeloTree significantly outperformed state-of-the-art methods (VeTra and CellPath) in recovering the correct tree topology.
  • Metrics: On bifurcating, trifurcating, and double-bifurcating trajectories, VeloTree achieved 88.6% – 93.1% accuracy in ordering cell pairs correctly, compared to 36.4% – 70.1% for VeTra and 44.8% – 78.5% for CellPath.
  • Reason for Superiority: Competing methods failed to assign pseudotime to a significant portion of cells (leaving them unassigned) and struggled with the hyperbolic nature of tree distances. VeloTree successfully assigned a global pseudotime to all cells.

• Real Data (Mouse Pancreas):

  • Applied to pancreatic progenitor differentiation into $\alpha, \beta, \delta, \epsilon$ cells.
  • The method correctly reconstructed the development of progenitors into $\beta$-cells.
  • It successfully captured the complex, non-tree-like origin of $\alpha$-cells (which can arise from both pre-endocrine cells and $\epsilon$-cells), distributing them across two branches of the inferred tree, consistent with biological literature.

5. Significance and Conclusion

• Robustness: By moving away from Euclidean distances and MSTs, VeloTree offers a more robust framework for inferring differentiation trees, particularly in noisy, high-dimensional data.
• Topological Focus: The method prioritizes recovering the topology of the differentiation tree (branching structure) rather than precise metric distances, which is often more biologically relevant.
• Future Directions: The authors note that the current method assumes a tree topology. Future work aims to extend the distance-based inference to cyclic topologies (e.g., cell cycles) and to infer weighted trees (accounting for varying differentiation speeds).

In summary, VeloTree represents a significant advancement in single-cell analysis by leveraging the geometric properties of RNA velocity fields through varifold distances, providing a mathematically rigorous and empirically superior method for reconstructing cellular differentiation trajectories.