Abstract
Rapid development of single cell RNA sequencing (scRNA-seq) technology has accelerated the exploration in biomedical researches. One of the focal interests in scRNA-seq data analysis is to classify cells into different types, which significantly assists in studying inter-cellular heterogeneity, such as cell types, cell states, and cell lineages, at the resolution of single cells. Although a number of tailored approaches have been developed for scRNA-seq data, their performance varies with different datasets and their clustering accuracy need to be improved. In this paper, we propose a novel ensemble clustering framework for scRNA-seq data called GRACE (GRAph-based Cluster Ensemble approach). First, we construct a highly reliable graph network for single cells by combining the clustering outcomes from five leading scRNA-seq data clustering methods. Then, we remeasure the relationships between cells by exploring the topology structure of network using random walk distance. Finally, we build a hierarchical cell-tree and obtain the clustering labels by cutting the tree structure into an appropriate number of sub-trees. Experimental results on twelve benchmark datasets show that GRACE has the higher clustering accuracy and is more robust among a variety of datasets than the state-of-the-art individual approaches. In addition, the graph structure of the network which is built upon the ensemble clusters is more reliable than the networks which are constructed according to the conventional similarity metrics.
Introduction
Single-cell RNA sequencing (scRNA-seq) has revolutionized biological research by enabling the analysis of gene expression at the resolution of individual cells. This capability is crucial for identifying rare cell types and understanding cellular heterogeneity. However, scRNA-seq data presents significant computational challenges: it is high-dimensional, noisy, and characterized by "dropouts" where gene expression is undetected.
While numerous clustering algorithms like Seurat, SC3, and SIMLR have been developed, their performance is often inconsistent across different biological contexts. A method that excels on one tissue type may perform poorly on another. This lack of robustness necessitates a more stable approach that leverages the strengths of multiple algorithms—a "wisdom of the crowd" strategy.
Methodology
The GRACE framework (GRAph-based Cluster Ensemble) addresses these challenges through a multi-stage pipeline designed to synthesize a consensus from diverse clustering methods.
The pipeline consists of five primary steps:
- Ensemble Generation: GRACE utilizes five state-of-the-art clustering methods: CIDR, SC3, t-SNE+k-means, Seurat, and SIMLR.
- Consensus Matrix Construction: An $n \times n$ matrix is generated where each entry $(i, j)$ records the frequency with which cell $i$ and cell $j$ are assigned to the same cluster across the five base methods.
- Graph Construction: A cell-to-cell graph is built where nodes represent cells. An edge is established between two cells only if a majority (at least three) of the base algorithms agree on their similarity, effectively filtering out algorithmic noise.
- Random Walk Distance: To capture the global topological structure, GRACE calculates random walk distances. This measure accounts for the multi-step connectivity between cells, providing a more nuanced similarity metric than simple local neighbors.
- Hierarchical Clustering and Automated Selection: A hierarchical "cell-tree" is constructed based on the random walk distances. The final number of clusters is determined automatically using a growth-rate formula applied to intra-cluster distances.
The framework was validated on 12 benchmark scRNA-seq datasets spanning various species (Human, Mouse), tissues (brain, bladder, pancreas), and sequencing technologies (10X Genomics, SMART-seq2).
Results and Discussion
GRACE demonstrated superior performance and robustness compared to individual state-of-the-art methods.
Accuracy and Stability
Using the Adjusted Rand Index (ARI) as a metric, GRACE achieved the highest accuracy in 10 out of 12 benchmark datasets. Its average ARI of 0.72 significantly outperformed the next best individual method, t-SNE+k-means (0.60). Notably, while individual methods like SC3 showed high variance in performance across datasets, GRACE remained consistently accurate, proving its robustness against the inherent instability of scRNA-seq data.
Topological Reliability
A key insight of this work is that the graph structure derived from an ensemble is more reliable than those built using traditional similarity metrics like Euclidean distance. By integrating multiple perspectives, GRACE filters out the biases of individual algorithms. Furthermore, the use of random walk distances allows the framework to identify subtle biological signals and rare cell types by considering the broader connectivity of the cell network.
Conclusion
GRACE provides a robust and accurate framework for scRNA-seq clustering by leveraging an ensemble-based graph approach. While the method introduces a slight computational overhead (approximately 5% over the base algorithms), the gains in stability and accuracy are substantial. Future work will focus on scaling the framework for massive datasets and applying it to clinical research, such as identifying malignant sub-types in cancer cell populations.
Summary updated