FastPG: Fast clustering of millions of single cells

Tom Bodenheimer, Mahantesh Halappanavar, Stuart R. Jefferys, Ryan Gibson, Siyao Liu, Peter J. Mucha, Natalie Stanley, Joel S. Parker, Sara R. SelitskybioRxiv 2020 · DOI

TL;DR

This paper introduces FastPG, a significantly faster version of the PhenoGraph algorithm for clustering millions of single cells. FastPG achieves comparable cell assignment accuracy to PhenoGraph while being up to 27x faster, making large-scale single-cell analysis more computationally feasible.

What Problem Does This Paper Address?

Single-cell analysis, particularly with technologies like mass cytometry, can generate massive datasets containing millions of cells. Unsupervised clustering is crucial for identifying distinct cell populations within these datasets. However, existing clustering algorithms, including the robust PhenoGraph, struggle with the computational demands of such large-scale data, leading to prohibitively long runtimes or requiring subsampling, which can sacrifice accuracy and the ability to detect rare cell types. This paper addresses the need for a clustering method that can efficiently handle millions of cells without compromising accuracy.

Methods

FastPG is a modification of the graph-based PhenoGraph algorithm. PhenoGraph typically involves three steps:

  1. k-Nearest Neighbor (kNN) Network Construction: Identifying neighboring cells based on their marker expression.
  2. Graph Weighting: Assigning weights to the connections in the network using the Jaccard index.
  3. Community Detection: Partitioning cells into clusters using the Louvain algorithm.

FastPG improves upon PhenoGraph by:

  • Replacing the kNN step: Using the Hierarchical Navigable Small World (HNSW) algorithm, which offers logarithmic scaling for faster approximate nearest neighbor searches.
  • Parallelizing the Jaccard index calculation: Implementing this step in C++ for multithreaded execution.
  • Replacing the Louvain algorithm: Utilizing Grappolo, a parallelized version of the Louvain algorithm optimized for shared-memory systems.

Datasets

The authors evaluated FastPG using several publicly available datasets:

  • Mass Cytometry Datasets:

    • Levine32 (104,184 cells)
    • Levine13 (81,747 cells)
    • Samusik01 (53,173 cells)
    • SamusikAll (514,386 cells) These datasets are referred to as "gold standard" due to their well-defined cell types. For evaluation, 20,000 cells were randomly subsampled from each dataset 20 times.
  • Single-cell RNA-seq (scRNA-seq) Datasets:

    • Zhengmix4eq (3,994 cells, 4 cell types)
    • Zhengmix8eq (3,993 cells, 8 cell types)
    • PBMC68k (68,545 cells, 11 cell types) The first two are "gold/silver standard" datasets with FACS-purified cell identities, while PBMC68k is a "silver standard" based on gene expression correlation.
  • Large-scale Runtime Benchmark Dataset:

    • FR-FCM-ZYT6 (38 million cells) This dataset was used to compare runtimes across a wide range of cell population sizes (1,000 to 20 million cells).

Key Insights and Ideas

  • The bottleneck is computation, not accuracy: The core insight is that the computational cost of clustering large single-cell datasets is the primary barrier, and algorithmic modifications can significantly improve speed without sacrificing the quality of cell assignments.
  • Leveraging efficient approximations and parallelization: By adopting HNSW for kNN, parallelizing computations, and using a parallel Louvain implementation, FastPG effectively tackles the computational challenge.
  • Broad applicability: FastPG demonstrates strong performance not only on mass cytometry data but also on scRNA-seq data, suggesting its utility across different single-cell modalities.
  • Enabling new analyses: The speedup offered by FastPG opens doors for more extensive computational experiments, such as consensus clustering or integrating multiple large datasets, which were previously impractical.

Key Results

  • Speed: FastPG is, on average, 27x faster than PhenoGraph and 7x faster than PARC. It clustered 20 million cells in 1.7 hours, compared to PARC's 8.6 hours.
  • Accuracy: FastPG achieved comparable cell assignment accuracy to PhenoGraph across mass cytometry datasets. It also showed higher cell assignment accuracy than PARC and FlowSOM on these datasets. For scRNA-seq data, FastPG's accuracy was nearly identical to Seurat.
  • F-measure: On mass cytometry datasets, FastPG and PhenoGraph generally achieved higher median F-measures (a metric combining precision and recall) than PARC and FlowSOM. For example, on Levine13, median F-measures were 0.89 for both FastPG and PhenoGraph, compared to 0.88 for PARC and 0.83 for FlowSOM.
  • scRNA-seq Performance: FastPG clustered 68,000 cells in 4.3 seconds, significantly outperforming Seurat's 246.8 seconds for the same task, while maintaining similar accuracy.

Limitations and Future Work

  • Limitations: The paper focuses on modifications to PhenoGraph's core components. While it demonstrates broad applicability, the specific performance on extremely sparse or noisy datasets might warrant further investigation. The paper mentions that "most clustering algorithms cannot efficiently handle a very large number of collected cells," implying that while FastPG is a significant improvement, there might still be limits to the absolute scale it can handle without further optimization or hardware considerations.
  • Future Work: The authors suggest that FastPG's speed and accuracy make it suitable for extensive computational experiments, such as consensus clustering, and for integrating cells across multiple samples without subsampling. This implies that future work could explore these advanced analytical workflows enabled by FastPG. The availability of the code also encourages community contributions and further development.

Summary updated

Abstract

Abstract Current single-cell experiments can produce datasets with millions of cells. Unsupervised clustering can be used to identify cell populations in single-cell analysis but often leads to interminable computation time at this scale. This problem has previously been mitigated by subsampling cells, which greatly reduces accuracy. We built on the graph-based algorithm PhenoGraph and developed FastPG which has the same cell assignment accuracy but is on average 27x faster in our tests. FastPG also has higher cell assignment accuracy than two other fast clustering methods, FlowSOM and PARC. Availability FastPG is available here: https://github.com/sararselitsky/FastPG
BibTeX
@misc{bodenheimer2020fastpg,
  author = {Tom Bodenheimer and Mahantesh Halappanavar and Stuart R. Jefferys and Ryan Gibson and Siyao Liu and Peter J. Mucha and Natalie Stanley and Joel S. Parker and Sara R. Selitsky},
  title = {{FastPG: Fast clustering of millions of single cells}},
  year = {2020},
  doi = {10.1101/2020.06.19.159749},
  howpublished = {bioRxiv},
}
Figure