Fast and memory-efficient scRNA-seq k-means clustering with various distances

Area of Science:

• Computational Biology
• Genomics
• Bioinformatics

Background:

• Single-cell RNA sequencing (scRNA-seq) analysis relies on clustering gene-by-cell expression matrices to identify cell populations.
• Existing methods can be computationally intensive for large scRNA-seq datasets.

Purpose of the Study:

• To develop and present minicore, a new open-source library for efficient k-means clustering of scRNA-seq data.
• To enable scalable and memory-efficient clustering of large-scale scRNA-seq datasets.

Main Methods:

• Implementation of k-means++ center finding and k-means clustering using a novel vectorized weighted reservoir sampling algorithm.
• Support for sparse count data and dense data, with various distance measures including Euclidean, Jensen-Shannon Divergence, Kullback-Leibler Divergence, and Bhattachaiyya distance.
• Development of a minicore pipeline utilizing k-means++, localsearch++, and mini-batch k-means for efficient clustering.

Main Results:

• Minicore achieves efficient k-means++ center finding for datasets up to 4 million cells in under 2 minutes.
• The library demonstrates memory efficiency, clustering 4 million cells using less than 10GiB of RAM.
• Comparison of distance measures reveals clusterings most consistent with known cell types.

Conclusions:

• Minicore provides a scalable and memory-efficient solution for clustering large scRNA-seq datasets.
• The library's performance enables atlas-scale clustering on commodity hardware.
• Findings offer guidance on selecting appropriate distance measures for scRNA-seq data clustering.