🧬 biology

scLodestar: Scalable probabilistic clustering of single cells in a continuous probability space

scLodestar is a scalable, high-performance framework that models single-cell data as continuous probability distributions over landmark states, enabling principled uncertainty quantification, the discovery of transitional cell populations, and efficient processing of millions of cells without the limitations of discrete hard clustering.

Original authors: Lingpin Pang, Yue Xu, Yunhua Zhao, Xuanhe Hou, Yue Ma, Huafeng Liu, Xiaoyu Liu, Han Wang, Luchun Yan, Chunjie Tian

Published 2026-07-06

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Lingpin Pang, Yue Xu, Yunhua Zhao, Xuanhe Hou, Yue Ma, Huafeng Liu, Xiaoyu Liu, Han Wang, Luchun Yan, Chunjie Tian

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ⚕️ This is an AI-generated explanation of a preprint that has not been peer-reviewed. It is not medical advice. Do not make health decisions based on this content. Read full disclaimer

Imagine you are trying to organize a massive library of books. In the old way of doing things (traditional single-cell clustering), you are forced to put every single book into exactly one shelf. If a book is a mix of "Science Fiction" and "History," you have to arbitrarily decide: "Okay, this goes on the Sci-Fi shelf." You lose the nuance of the book being a blend of both.

scLodestar is a new, smarter way to organize these "books" (which, in this case, are individual cells from your body). Instead of forcing a cell into one box, scLodestar gives every cell a membership card that says exactly how much it belongs to several different groups at once.

Here is how it works, broken down with simple analogies:

1. The "Landmarks" (The Reference Points)

First, the system picks a few special "landmark" cells. Think of these like the main cities on a map (e.g., New York, London, Tokyo). These aren't just random points; they are carefully chosen to represent the most distinct types of cells in your sample.

The Innovation: Instead of just picking the "average" city, scLodestar picks real, existing cells to be these landmarks, ensuring they are true representatives.

2. The "Probability Space" (The Map)

In the old method, a cell is either "New York" or "London." In scLodestar, a cell is a location on a map between these cities.

If a cell is a pure "New York" cell, it sits right on top of the New York landmark.
If a cell is a "transitional" cell (maybe a young cell that is starting to become a New York cell but still has some London traits), it sits somewhere in the middle of the map.
The Result: You can see the "journey" cells are taking. You don't just see the start and finish; you see the smooth road connecting them.

3. The "Random Walk" (How it figures out the location)

How does the system know where a cell belongs on this map? It uses a method called Random Walk with Restart.

The Analogy: Imagine a tourist starting at the "New York" landmark. They take random steps to neighboring cells. Sometimes, they get "teleported" back to New York. Over time, if a cell is very close to New York, the tourist will visit it often. If a cell is far away, they visit it rarely.
By doing this for all the landmarks, the system calculates a "score" for every cell, telling us exactly how much it feels like New York, how much it feels like London, etc. This creates that probability card mentioned earlier.

4. Why This is Better (The Superpowers)

The paper highlights three main things this new map allows us to do:

Spotting the "In-Betweens": Because cells aren't forced into one box, scLodestar can easily spot cells that are in the middle of changing (transitional states). In the old method, these cells would be hidden or mislabeled. Here, they are clearly visible as "mixed" colors on the map.
Faithful "Denoising" (Fixing the Noise): Single-cell data is often "noisy" (like a radio with static). Some cells might accidentally show a gene turning on when it shouldn't.
- The Analogy: If you have a blurry photo of a cat, you might guess it's a dog. But if you know the photo is 90% "Cat" and 10% "Dog," you can fix the photo to look like a cat without accidentally turning it into a dog.
- scLodestar uses the probability scores to smooth out the noise. If a cell has almost zero "membership" to a specific group, the system won't give it the traits of that group. This prevents "hallucinations" (making up data that isn't there).
Speed: Usually, doing this kind of complex math on millions of cells takes hours or days. The authors wrote special, super-fast computer code (in a language called C) to make it happen.
- The Claim: They processed 3 million cells (a huge dataset) in just five minutes. That's like organizing a library the size of a city in the time it takes to brew a cup of coffee.

5. Mixing Different Libraries (Batch Correction)

Often, scientists have data from different experiments (different "batches") that look slightly different due to technical reasons, not biology.

The Analogy: Imagine two libraries where the same book has a slightly different color cover depending on which library it came from.
scLodestar aligns these libraries by matching the "probability maps" rather than the raw data. It successfully mixes the data from different donors so that the biology stands out, while the technical differences fade away.

Summary

scLodestar is a tool that stops forcing cells into rigid boxes. Instead, it places every cell on a smooth, continuous map where it can belong to multiple groups at once. It does this incredibly fast, finds the "in-between" cells that others miss, and cleans up noisy data without making things up. It turns a black-and-white list of categories into a colorful, detailed map of cellular life.

Technical Summary of scLodestar

Problem Statement
Conventional single-cell RNA sequencing (scRNA-seq) analysis relies on "hard" clustering algorithms (e.g., Leiden, Louvain) that assign each cell to a single, discrete cluster. The authors argue that this paradigm imposes an artificial discreteness on biological reality, where cells often exist in continuous differentiation trajectories, co-express markers of multiple lineages, and occupy transitional states. Hard clustering obscures this heterogeneity, forces arbitrary boundary decisions, and fails to provide principled uncertainty quantification. Furthermore, existing alternatives—such as soft clustering, trajectory inference, or deep generative models—often lack scalability to atlas-sized datasets, fail to provide interpretable memberships, or require prior knowledge of directionality.

Methodology
scLodestar (Single Cell Landmark-based Teleportation Markov Chain Clustering) proposes a framework where each cell is represented not as a discrete label, but as a probability distribution over a set of $L$ "landmark" states within a probability simplex $\Delta_{L-1}$ . The workflow consists of three primary stages:

Graph Construction: A shared nearest neighbor (SNN) graph is constructed from cell embeddings (typically PCA coordinates). Edge weights are determined by Jaccard similarity of neighbor sets, followed by optional pruning and anisotropic renormalization to handle density heterogeneity.
Density-Aware Landmark Selection: Representative cells (landmarks) are selected via k-medoids clustering. To ensure sparse regions are represented, the method employs density-aware oversampling, weighting low-density cells higher during the selection process. The authors introduce a custom OneBatchPAM algorithm to accelerate this step.
Projection via Random Walk with Restart (RWR): Cells are projected into the probability simplex using personalized PageRank. A random walker starts at a landmark and, with probability $\alpha$ , teleports back to that landmark, or with probability $1-\alpha$ , transitions to a neighbor based on SNN weights. The stationary distribution of this walk for each landmark defines the membership probabilities for all cells. This is solved via power iteration on a sparse matrix.

Key Technical Contributions

Probabilistic Representation: Instead of discrete labels, scLodestar outputs a membership vector $m_i \in \Delta_{L-1}$ $m_{i} \in Δ_{L - 1}$ for each cell. This allows for:
- Uncertainty Quantification: Assignment uncertainty is measured via entropy ( $H_i$ ) and probability margin ( $\Delta_i$ ), identifying transitional or ambiguous cells.
- Continuous Marker Identification: Genes are identified by correlating expression with continuous membership vectors rather than discrete groups, capturing gradual expression changes.
- Faithful Imputation: Gene expression is imputed as a Dirichlet-weighted average of landmark expression profiles. This prevents "hallucination" (assigning expression patterns to cells with zero affinity for a state).
Scalability via Custom Kernels: To address the computational cost of probabilistic methods on large datasets, the authors implemented two high-performance C/Cython kernels:
- OneBatchPAM: Accelerates landmark selection by 400-fold compared to standard k-medoids (BanditPAM) using batched distance computations and early termination.
- Sparse CSR-Optimized RWR: Accelerates the random walk computation by 100-fold compared to NetworkX implementations by leveraging Compressed Sparse Row (CSR) matrix operations.
Probability-Space Batch Correction: The method integrates multi-sample data by aligning probability distributions in the simplex rather than raw expression space, leveraging the inherent normalization of probability vectors to reduce sensitivity to technical variation.

Results
The authors validated scLodestar across four diverse datasets:

Human Bone Marrow (17k cells): The method identified 26 landmark clusters and revealed transitional populations with high entropy that were obscured by hard clustering. It enabled color-blended visualizations of cellular continua and correlation-based marker detection.
10x Genomics 3k PBMCs: Demonstrated confidence-based cell selection (filtering ambiguous cells) and faithful gene imputation. For markers like Ptprc and Reln, imputation removed background noise without introducing spurious signals in negative populations.
Mouse Embryonic Mesoderm (3 million cells): The pipeline processed 3 million cells in approximately five minutes. It achieved high purity (0.78) and homogeneity (0.68) against author annotations, successfully capturing complex developmental trajectories and subtypes (e.g., chondrocyte subtypes).
Diabetic Kidney Disease (14 donors): In a batch correction benchmark against Harmony, scLodestar achieved superior batch mixing (higher iLISI and KBET scores) while maintaining competitive biological conservation metrics.

Significance and Claims
The paper claims that scLodestar provides a unified framework that bridges the gap between biological nuance and computational scalability. By representing cellular identity as a full probability distribution, it resolves the tension between the continuous nature of differentiation and the discrete requirements of standard analysis pipelines.

The authors emphasize that their approach:

Reveals Hidden Biology: Uncovers transitional populations and gradual expression changes invisible to hard clustering.
Ensures Fidelity: Prevents the "hallucination" artifacts common in aggressive imputation methods by anchoring denoising in probabilistic membership.
Scales to Atlas Size: Through algorithmic co-design (OneBatchPAM and CSR-RWR), it makes probabilistic clustering feasible for datasets containing millions of cells, processing 3 million cells in five minutes.
Offers a New Integration Paradigm: Suggests that aligning cells in probability space is a viable and often superior alternative to expression-space alignment for removing batch effects.

The authors conclude that this probabilistic paradigm shifts the field toward uncertainty-aware analyses, enabling more faithful representations of cellular identity as it continues to scale to atlas-level datasets.