Scaling Spatial and Single-Cell Omics to Millions of Cells

154 concepts130 papers1 proposal

Modern biology is undergoing a data explosion. The transition from bulk tissue sequencing to single-cell RNA sequencing (scRNA-seq) allowed researchers to profile thousands of individual cells. Today, high-throughput spatial transcriptomics (ST) platforms go even further, capturing both the genetic profiles and the precise physical coordinates of millions of cells within an intact tissue slice.

While these technologies offer an unprecedented view of tissue architecture, they have triggered a severe computational crisis. Many foundational statistical methods in bioinformatics were designed for datasets with a few hundred samples. When applied to modern, atlas-scale datasets containing millions of observations, these algorithms hit a hard wall of computational complexity, resulting in prohibitive runtime delays or out-of-memory crashes.

To build pipelines capable of processing whole-organ or clinical-scale datasets, a major research direction focuses on redesigning omics algorithms to achieve linear scalability.

The Quadratic Trap: Why Traditional Methods Fail

To understand why traditional algorithms fail to scale, we must look at how they handle relationships between data points. In single-cell and spatial analysis, common tasks include identifying cell types, finding spatially variable genes, and mapping cellular trajectories.

Many classical approaches rely on pairwise comparisons. If a dataset contains $N$ cells, an algorithm might calculate a distance or correlation matrix comparing every cell to every other cell. As noted by Benjamin L. Walker et al. in Deciphering tissue structure and function using spatial transcriptomics, these methods scale with quadratic complexity ($\mathcal{O}(N^2)$), or even cubic complexity ($\mathcal{O}(N^3)$) in the case of certain Bayesian frameworks.

$$\text{Pairwise Comparisons} \propto N^2$$

When $N = 10,000$, a quadratic algorithm performs roughly 100 million operations—a trivial task for modern computers. But when technologies scale to $N = 1,000,000$, $N^2$ skyrockets to one trillion operations. As highlighted by Felix Drost et al. in Multi-modal generative modeling for joint analysis of single-cell T cell receptor and gene expression data, this pairwise dependency causes memory and time requirements to grow exponentially, rendering atlas-level analysis impossible on standard laboratory hardware.

A comprehensive evaluation by Xuanwei Chen et al. in Benchmarking algorithms for spatially variable gene identification in spatial transcriptomics confirmed this bottleneck empirically: many specialized spatial algorithms routinely exceed 24-hour execution windows or crash entirely when confronted with modern high-resolution datasets.

Sparsification via Localized Kernels

The key to breaking the quadratic bottleneck is realizing that global pairwise comparisons are biologically and mathematically wasteful. In an intact tissue, a cell interacts intensively with its immediate neighbors, but it is independent of cells located millimeters away on the opposite side of the slide.

By replacing global dense matrices with localized sparse representations, algorithms can achieve linear complexity ($\mathcal{O}(N)$).

The authors of BANKSY unifies cell typing and tissue domain segmentation for scalable spatial omics data analysis, led by Vipul Singhal, leverage this insight to unify cell typing and tissue domain segmentation. Instead of computing a global spatial covariance matrix, their framework constructs a localized neighborhood kernel. Each cell's own expression profile is augmented purely with the average profile of its immediate spatial neighbors. Because the size of the local neighborhood remains constant regardless of how many cells are added to the experiment, the computational complexity scales linearly with the number of cells, allowing millions of cells to be clustered in minutes.

Data Compression via Vector Quantization

Another powerful strategy for scaling single-cell analysis is reducing the effective $N$ itself without losing rare biological signals. While a dataset might contain millions of individual sequencing reads, many cells share nearly identical transcriptomic states.

Rather than processing every redundant cell individually, modern frameworks compress the data into "metacells." As demonstrated by Yunfan Li et al. in MetaQ: fast, scalable and accurate metacell inference via single-cell quantization, this can be achieved efficiently using vector quantization.

Vector quantization maps continuous, high-dimensional cell expression profiles into a discrete set of representative vectors (a codebook). By optimizing this codebook to minimize distortion, the algorithm groups highly similar cells into compact, statistically robust aggregates while preserving rare cell types that would be obliterated by simple downsampling. This approach achieves linear runtime and constant memory usage, shifting the computational burden away from infrastructure limitations.

Decoupling and Modular Priors

Traditional spatial omics models often hard-code spatial coordinates directly into complex joint optimization loops, forcing the system to recompute spatial relationships at every iteration of data imputation or dimensionality reduction.

To eliminate this overhead, researchers have introduced modular frameworks that decouple the spatial architecture from the underlying omics model. In Smoother: a unified and modular framework for incorporating structural dependency in spatial omics data, Jiayu Su et al. treat spatial proximity as a reusable mathematical prior rather than a rigid constraint. By formulating spatial structure as a plug-and-play loss function, any non-spatial model can be "spatialized" without altering its core architecture. This decoupling allows the framework to exploit fast, specialized numerical solvers, enabling interactive exploratory analysis on standard personal computers.

A similar decoupling strategy is used to scale trajectory inference. In CellRank 2: unified fate mapping in multiview single-cell data, Philipp Weiler et al. scale cellular fate mapping to millions of cells by strictly separating the initial transition probability modeling from downstream analysis. By isolating the computationally intensive step of estimating directional cell-to-cell transitions into a single, highly optimized phase, the framework prevents downstream biological queries from triggering repeated, expensive matrix recalculations.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_computational_scalability_computational__0a631139,
  title = {computational scalability (computational scalability bottleneck)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/computational-scalability-computational-scalability-bottleneck/rdr_0a6311391fc044929bc0534b6b3fb1b9},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_computational_scalability_computational__0a631139_v1,
  title = {computational scalability (computational scalability bottleneck)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/computational-scalability-computational-scalability-bottleneck/rdr_0a6311391fc044929bc0534b6b3fb1b9/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake