🧬 biology

Efficient Imputation for Patch-based Missing Single-cell Data via Cluster-regularized Optimal Transport

This paper introduces CROT, a cluster-regularized optimal transport algorithm that efficiently and accurately imputes large patches of missing data in high-dimensional single-cell sequencing datasets while significantly reducing runtime compared to existing methods.

Original authors: Yuyu Liu, Jiannan Yang, Ziyang Yu, Weishen Pan, Fei Wang, Tengfei Ma

Published 2026-05-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yuyu Liu, Jiannan Yang, Ziyang Yu, Weishen Pan, Fei Wang, Tengfei Ma

Original paper licensed under CC BY 4.0 (http://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

The Problem: The "Missing Puzzle Pieces"

Imagine you are trying to solve a massive, complex jigsaw puzzle that represents the inner workings of a single cell. In the world of single-cell sequencing (a technology that reads the genetic instructions of individual cells), this puzzle is often incomplete.

Sometimes, the puzzle pieces are missing because the cell genuinely didn't have a specific instruction (a biological fact). But often, the pieces are missing because the camera used to take the picture was too dim, or the scanner glitched (technical errors). This is called a "dropout."

Most existing methods try to guess the missing pieces by looking at the neighbors. If a piece is missing, they ask, "What do the pieces right next to it look like?" This works okay for a few missing spots. But what if an entire corner of the puzzle is gone? Or what if an entire type of puzzle piece (like all the blue sky pieces) is missing from one specific box of the puzzle?

This is the "patch-based missing data" problem the paper addresses. It happens when a whole batch of data fails to record a specific type of information (like all protein measurements for a group of cells). Traditional methods get confused here because they can't just look at "neighbors" to fill in a whole missing section.

The Solution: CROT (The "Smart Matchmaker")

The authors propose a new method called CROT (Cluster-Regularized Optimal Transport). Think of CROT as a highly skilled matchmaker that tries to rebuild the missing puzzle pieces by comparing them to a "perfect" reference puzzle.

Here is how it works, broken down into two main steps:

1. The "Optimal Transport" (The Moving Truck)
Imagine you have a truck full of furniture (the complete, perfect data) and a house with empty rooms (the incomplete data with missing pieces). "Optimal Transport" is the math that figures out the most efficient way to move the furniture from the truck to the house to fill the empty rooms. It doesn't just throw furniture in randomly; it calculates the cheapest, most logical path to move every item so the house looks as much like the truck's inventory as possible.

2. The "Cluster Regularization" (The Room Arrangement)
Here is the clever twist. If you just move furniture randomly, you might put a bed in the kitchen and a stove in the bedroom. The house is full, but it's messy and doesn't make sense.

In biology, cells of the same type (like T-cells or B-cells) are like "families" that should stay together. CROT adds a rule called Cluster Regularization. It says: "Before you move the furniture, make sure you keep the families together."

It groups the cells into "families" (clusters) based on their characteristics. Then, it ensures that when it moves data from the complete set to the incomplete set, it moves the "T-cell family" to the "T-cell family" and the "B-cell family" to the "B-cell family." This prevents the method from accidentally mixing up different cell types, which would ruin the biological meaning of the data.

Why It's Better (The Results)

The paper tested CROT on three real-world datasets (CITE-seq, Multiome, and PBMC) where they intentionally hid large blocks of data to see if the method could find it.

Accuracy: CROT was better at guessing the missing numbers than other top methods. It didn't just guess "average" numbers; it guessed numbers that fit the specific "family" of the cell.
Speed: This is a huge win. While other methods took minutes (or even hours) to fill in the missing data, CROT did it in seconds.
- Analogy: If other methods are like a team of painters carefully hand-painting every missing brick, CROT is like a high-speed 3D printer that instantly reconstructs the missing wall.
Structure: When they looked at the results visually (using a map called UMAP), the cells organized themselves into neat, distinct groups. Other methods made the groups look blurry or mixed together. CROT kept the groups sharp and distinct.

The Catch (Limitations)

The paper is honest about where CROT might struggle:

Batch Effects: If the "perfect reference puzzle" and the "missing puzzle" come from two totally different labs with different lighting and camera angles, CROT might get confused. It assumes the two datasets are mostly similar, just missing pieces.
Missing Families: If the "missing puzzle" is missing an entire type of cell (e.g., no T-cells at all in the target data), CROT can't invent a T-cell family out of thin air. It needs at least some reference to know what a T-cell looks like.

Summary

In short, the paper presents CROT, a fast and smart tool for fixing single-cell data. It fixes the problem of "big chunks" of missing data by using math to move information from a complete dataset to an incomplete one, while strictly enforcing that different cell types stay in their own distinct groups. It is faster and more accurate than current methods, making it a powerful tool for analyzing large biological datasets.

Technical Summary: Efficient Imputation for Patch-based Missing Single-cell Data via Cluster-regularized Optimal Transport

1. Problem Statement

Single-cell sequencing technologies generate high-dimensional data that are notoriously sparse due to "dropout" events (technical zeros) and biological lack of expression. While numerous imputation methods exist, they typically assume uniform missingness or data completeness. They often struggle with patch-based missing data, a scenario where entire blocks of features (e.g., all protein measurements in a CITE-seq batch or all gene expression values in a specific modality) are absent for a subset of the dataset.

Existing methods often rely on local similarities or strong assumptions about data completeness, leading to over-smoothing (blurring biological distinctions) or failure to recover structured absences. Furthermore, many approaches lack the computational efficiency required for large-scale datasets, often requiring minutes to hours for imputation.

2. Methodology: CROT

The authors propose Cluster-Regularized Optimal Transport (CROT), an algorithm designed to impute missing values in tabular single-cell data by aligning an incomplete dataset ( $X_2$ ) with a complete reference dataset ( $X_1$ ).

Core Mechanism

CROT formulates imputation as an optimization problem that minimizes the distance between the distributions of the incomplete and complete data while preserving biological structure. The method utilizes Entropic Optimal Transport (OT) to compute a transport plan that maps features from $X_1$ to $X_2$ .

The total loss function, $L_{CROT}$ , consists of two terms:

Data-Level Alignment: The Sinkhorn divergence ( $S^\epsilon_p$ ) between the raw data distributions of $X_1$ and $X_2$ . This ensures the imputed values align with the observed distribution.
Cluster-Regularization: A regularization term ( $\alpha S^\epsilon_p$ ) that minimizes the Sinkhorn divergence between the cluster centroids of $X_1$ and $X_2$ .

Algorithmic Workflow

Initialization: Missing entries in $X_2$ are initialized using the column means of $X_1$ plus Gaussian noise.
Cluster Determination: The optimal number of clusters ( $k$ ) is determined for the reference data $X_1$ using the Elbow method and applied to $X_2$ .
Alternating Optimization:
- Clustering Step: K-means clustering is performed on sampled subsets of $X_1$ and the current estimate of $X_2$ to assign cluster labels and compute centroids ( $C_1, C_2$ ). Note that the discrete assignment step is non-differentiable; thus, assignments are held fixed during the gradient update.
- Transport Step: The Sinkhorn divergence is computed for both the data samples and the cluster centroids.
- Update: The missing entries in $X_2$ are updated via gradient descent (using the Adam optimizer) to minimize the combined loss.
Convergence: The process iterates until the loss converges, typically within 150 iterations.

Complexity

The algorithm employs mini-batching (sampling $l$ rows) to ensure scalability. The overall time complexity is $O(m_1 \cdot n + T \cdot l^2)$ , where $m_1$ is the number of cells in the reference, $n$ is the number of features, $T$ is the number of outer iterations, and $l$ is the batch size. This linear dependence on dataset size allows for significant speedups compared to full-matrix OT approaches.

3. Key Contributions

Novel Framework: Introduction of CROT, the first optimal transport-based imputation method specifically designed to handle patch-based missingness (entire modality blocks) in single-cell data.
Structural Preservation: The integration of a cluster-regularization term ensures that the imputed data recapitulates the cell-type structure (centroids) of the reference data, preventing the collapse of distinct cell identities.
Efficiency: The method achieves superior imputation accuracy with drastically reduced runtime (seconds vs. minutes/hours for baselines) by leveraging entropic regularization and mini-batch optimization.
Robust Evaluation: Comprehensive evaluation on three real-world datasets (CITE-seq, Multiome, PBMC) under simulated patch-based dropout scenarios.

4. Experimental Results

The authors evaluated CROT against state-of-the-art baselines including MAGIC, scImpute, DeepImpute, totalVI, MultiVI, and SCOTv2.

Numerical Recovery: CROT achieved the highest Pearson Correlation Coefficient (PCC) and lowest Mean Absolute Error (MAE) and Root Mean Square Error (RMSE) across all three datasets. For example, on the CITE-seq dataset, CROT achieved a PCC of $0.76 \pm 0.04$ and MAE of $0.47 \pm 0.02$ , outperforming the next best method (totalVI).
Clustering Performance: In terms of cell-type clustering (measured by Adjusted Rand Index, NMI, and Purity), CROT consistently outperformed other methods. On CITE-seq, it achieved an ARI of $0.83$ and Purity of $0.93$, significantly higher than raw data or other imputation methods.
Biological Fidelity: Visualizations (UMAP) and marker protein expression analysis (e.g., CD3, CD14, CD19) confirmed that CROT preserves biological heterogeneity and cell-type-specific signatures better than competitors, which often showed attenuated marker specificity.
Computational Efficiency: CROT demonstrated exceptional speed, completing imputation in 5, 12, and 39 seconds for CITE-seq, Multiome, and PBMC datasets, respectively. This represents approximately 1–2% of the runtime required by the average baseline method.
Ablation and Robustness:
- Ablation studies confirmed that both the data-level loss and the cluster-regularization term are necessary for optimal performance.
- Sensitivity analysis showed the method is robust to variations in the regularization strength ( $\alpha$ ) and the number of clusters ( $k$ ).
- Robustness tests indicated that while performance degrades gracefully under partial random missingness (50-75% masking) and mismatched cluster compositions (missing cell types), it remains competitive, though the method assumes similar biological composition between reference and target.

5. Significance and Claims

The paper claims that CROT provides a robust solution for imputation in heterogeneous, high-dimensional datasets with structured data absence, addressing a critical gap where traditional dropout-focused algorithms fail.

The authors emphasize that by coupling optimal transport with cluster-level regularization, CROT effectively balances numerical accuracy with biological structural preservation. The method is presented as a practical, scalable tool for large-scale, multimodal single-cell analysis, capable of recovering meaningful biological signals (such as rare cell subpopulations and developmental trajectories) that are often obscured by noise or missing data. The authors acknowledge limitations regarding explicit batch correction and dependence on the reference data sharing similar biological composition, suggesting these as areas for future refinement.