bioRxivBioinformaticsPreprint
K-nearest neighbor smoothing for high-throughput single-cell RNA-Seq data
Abstract
High-throughput single-cell RNA-Seq (scRNA-Seq) is a powerful approach for studying heterogeneous tissues and dynamic cellular processes. However, compared to bulk RNA-Seq, single-cell expression profiles are extremely noisy, as they only capture a fraction of the transcripts present in the cell. Here, we propose the k-nearest neighbor smoothing (kNN-smoothing) algorithm, designed to reduce noise by aggregating information from similar cells (neighbors) in a computationally efficient and statistically tractable manner. The algorithm is based on the observation that across protocols, the technical noise exhibited by UMI-filtered scRNA-Seq data closely follows Poisson statistics. Smoothing is performed by first identifying the nearest neighbors of each cell in a step-wise fashion, based on partially smoothed and variance-stabilized expression profiles, and then aggregating their transcript counts. We show that kNN-smoothing greatly improves the detection of clusters of cells and co-expressed genes, and clearly outperforms other smoothing methods on simulated data. To accurately perform smoothing for datasets containing highly similar cell populations, we propose the kNN-smoothing 2 algorithm, in which neighbors are determined after projecting the partially smoothed data onto the first few principal components. We show that unlike its predecessor, kNN-smoothing 2 can accurately distinguish between cells from different T cell subsets, and enables their identification in peripheral blood using unsupervised methods. Our work facilitates the analysis of scRNA-Seq data across a broad range of applications, including the identification of cell populations in heterogeneous tissues and the characterization of dynamic processes such as cellular differentiation. Reference implementations of our algorithms can be found at https://github.com/yanailab/knn-smoothing.
- organism: human
- organism: mouse
- assay: scRNA-seq
- research focus: imputation
- research focus: clustering
- research focus: software / tool
- research focus: differential expression
- approach: machine learning (classical)
- approach: statistical model
- approach: simulation
In-depth summary
Claude Opus 5.5 · xhigh effort · 17 Oct 2026 · from the full text of version 3 (9 Apr 2018) · CC BY-NC 4.0
Aggregating UMI counts from a cell's nearest neighbours, chosen step-wise on variance-stabilised profiles, cuts technical noise enough that PCA and hierarchical clustering resolve cell types and T cell subsets.
Droplet-based single-cell libraries capture only a small share of a cell's transcripts, so per-cell profiles are too noisy for the standard exploratory toolkit, and most denoising methods assume an excess of zeros beyond what a count distribution predicts. The authors argue that UMI-filtered counts are simply Poisson after normalising for capture efficiency, which licenses a fix with no parametric model: sum counts over neighbours and keep Poisson statistics.
Key results
ShownSmoothing before dimensionality reduction tightens cell type structure on real droplet datasets and makes hierarchical clustering workable, with marker genes showing cleaner type-restricted expression.
On inDrop pancreatic islet data (2,109 cells) with k=15, variance in the first two PCs rose from 20.8% to 40.3%. On 4,340 Chromium PBMCs with k=127 it rose from 16.6% to 70.4%, and marker thresholds assigned 93% of cells to T cell, CD14 monocyte, B cell or dendritic identities. Clustering the unsmoothed data gave less coherent groups. · Application of kNN-smoothing to scRNA-Seq data…; Application of kNN-smoothing to scRNA-Seq data…
ShownThe first algorithm picks wrong neighbours when populations are transcriptionally close; choosing neighbours in principal component space fixes this and lets unsupervised analysis split T cell subsets.
In mixtures of 1,000 naive CD4 cells with 1,000 naive CD8 or memory CD4 cells the first two PCs held 2.7% and 1.4% of variance and smoothing blurred the groups. With k=127 and d=5 the first PC separated them, capturing 19.5% and 30.9%. On a pan-T dataset of 4,583 profiles naive and memory markers formed exclusive clusters, and re-running on the 1,656 naive cells split CD4 from CD8. · The kNN-smoothing algorithm fails to accurately…; An improved smoothing algorithm accurately…; kNN-smoothing 2 facilitates the identification…
SuggestedOn datasets simulated from real data the method recovers the generating profile more closely than two published imputation methods, over a wide range of k.
Median Pearson correlation with the true cluster profile on SIM-PANCREAS was approx. 0.93 at k=15 and approx. 0.98 at k=63, versus best-case approx. 0.85 for MAGIC and approx. 0.87 for scImpute across all settings tried; the margin was larger on SIM-PBMC and held under RMSE and square-root transformation. Accuracy dropped once k exceeded the cluster size. · Comparison with other smoothing methods on…; Use of simulation studies to quantify the…
ShownTechnical variation in UMI-filtered droplet data is consistent with Poisson sampling on top of per-droplet capture efficiency, with no sign of the extra zeros that competing models assume.
Control droplets holding identical RNA pools on inDrop, Drop-Seq and 10x gave the expected CV-mean slope after normalising each profile to the median count, and observed zero frequencies matched the Poisson prediction for inDrop and 10x; Drop-Seq sat slightly high, fitting a scaled Poisson. Averaging non-overlapping sets of 16 of 935 inDrop profiles into 58 profiles cut variation four-fold. · The normalized UMI counts of replicate scRNA-Seq…; Aggregation of n replicate profiles results in…
ShownBoth algorithms run on ordinary hardware for datasets of a few thousand cells, unlike one of the compared imputation methods.
Subsampling a Chromium dataset of 21,425 genes to between 2,000 and 8,000 cells on a laptop gave runtimes from seconds to just over 14 minutes (k=511, n=8,000), rising linearly with k; the authors estimate ceilings near 5k, 10k and 20k cells for machines with 4, 8 and 16 GiB. scImpute routinely ran for hours even on 4 CPU cores. · Python implementations of kNN-smoothing and…; Comparison of the accuracies of kNN-smoothing…
Methods, data and reproducibility
Counts are normalised to the median total per cell and Freeman-Tukey transformed; neighbours are then found step-wise on partially smoothed profiles with k growing each round, and each cell's counts are summed with its k neighbours'. The second version projects onto the first d principal components before measuring distance. Evaluation used real droplet data and datasets simulated from it.
- inDrop droplets containing pure RNA from K562 cells, used as technical replicates to test the noise model · human · n = 935 droplets, 19,865 protein-coding genes · SRX863258
- inDrop profiles of pancreatic islet tissue from one donor, the PANCREAS dataset, with at least 14 cell populations · human · n = 2,109 cells · SRX1935938
- 10x Genomics Chromium v2 peripheral blood mononuclear cells from a healthy donor, processed with Cell Ranger, the PMBC dataset · human · n = 4,340 cells, 19,765 genes after filtering
- ERCC spike-in droplet data used for the noise analysis: one 10x set and one Drop-Seq set · n = 92 spike-ins / 1,015 droplets; 80 spike-ins / 84 droplets · GSM1629193
- Bead-enriched T cell subset datasets from 10x (helper, regulatory, naive and memory CD4, cytotoxic and naive CD8), combined and subsampled, plus a pan-T cell dataset · human · n = 6,000 cells over 19,208 genes; pan-T set 4,583 profiles
- Myeloid progenitor UMI counts with published cluster labels, used in supplementary analysis · mouse · n = 27,297 cells with cluster labels · GSE72857
- SIM-PANCREAS and SIM-PBMC: 10-cluster datasets simulated from the real ones by drawing Poisson counts around cluster means scaled to each cell's observed depth · n = matched to the source datasets
- Methods & tools
- kNN-smoothing, kNN-smoothing 2, MAGIC, scImpute, STAR, Cell Ranger, scikit-learn, scipy, fastq-dump, inDrop, Drop-Seq, 10x Genomics Chromium
- Reagents & environment
- Python v3.5.4 (kNN-smoothing) and v3.6.4 (kNN-smoothing 2) on Ubuntu 17.10; scikit-learn v0.19.1; scipy v1.0.0; STAR 2.5.3a; Cell Ranger 2.1.0 and 1.1.0; MAGIC at commit 4d5efb4; scImpute v0.0.4 at commit dda0441.
- Assay conditions & compute
- Runtimes were measured on a laptop with an Intel Core i7-6600U and 20 GiB of memory. The implementation holds three copies of the expression matrix and two n-by-n arrays, which sets the cell-count ceilings quoted for 4, 8 and 16 GiB machines.
- Reproducibility gaps
- The pointers to reference implementations, the 10x download pages and the MAGIC cluster labels are truncated here, so no URL can be given. Accessions are printed for several datasets (SRX863258, SRX1935938, GSM1629193, GSE72857) but the 10x datasets are named rather than accessioned.
Limitations (6)
- Smoothed profiles are no longer statistically independent across cells, so the authors warn against feeding them straight into differential expression tests. · stated by the authors
- Choosing k too large averages across populations and can produce profiles that match no real cell population; the authors offer heuristics but no objective criterion, treating the method as exploratory. · stated by the authors
- The simulation framework drops within-type biology such as cell cycle phase and cannot represent continuous processes like differentiation, so accuracy there is untested. · stated by the authors
- Scaling is limited by the full pairwise distance matrix, which the authors expect to exceed memory for tens or hundreds of thousands of cells. · stated by the authors
- The Poisson noise claim is expected to hold for protocols that count end-tagged transcripts with UMI filtering and not for others, which the authors state needs further investigation. · stated by the authors
- The comparison with MAGIC and scImpute rests on simulations the authors designed around their own noise model, which is the same assumption their method is built on. · noted in this summary
Read this if you denoise droplet scRNA-seq before clustering or dimensionality reduction, need to separate closely related subsets such as T cells, or care whether UMI counts are really zero-inflated.
- Citations
- 134
Reproducibility ledger
Nobody has reported trying to reproduce this paper yet. Did you replicate an experiment or run the code? Your report saves the next lab a week.
Sign in to file a reproducibility report.
Related papers
- New algorithms for unsupervised cell clusteringfrom scRNA-seq data
Melissa Robles, Jorge Díaz-Riaño, … Jorge Duitama·Bioinformatics AdvancesPeer-reviewed·Jan 1, 2026
- netSmooth: Network-smoothing based imputation for single cell RNA-seq
Jonathan Ronen, Altuna Akalin·F1000ResearchPeer-reviewed·Jan 3, 2018
- A completely parameter-free method for graph-based single cell RNA-seq clustering
Maryam Zand, Jianhua Ruan·bioRxiv·Jul 15, 2021
- Clustering single-cell RNA-seq data by rank constrained similarity learning
Qinglin Mei, Guojun Li, Zhengchang Su·BioinformaticsPeer-reviewed·Apr 23, 2021
- A Fully Automated, Data-Driven Approach for Dimensionality Reduction and Clustering in Single-Cell RNA-seq Analysis
Hyun Kim, Faeyza Rishad Ardi, … Jae Kyoung Kim·Computer Methods and Programs in Biomedicine UpdatePeer-reviewed·Jan 26, 2026
- MetaCell: analysis of single cell RNA-seq data using k-NN graph partitions
Yael Baran, Akhiad Bercovich, … Amos Tanay·Genome biologyPeer-reviewed·Oct 11, 2019