Parallelized Inference for Single Cell Transcriptomic Clustering with Split Merge Sampling on DPMM Model

Tiehang Duan, José Pinto, Xiaohui XiebioRxiv 2018 · DOI

TL;DR

This paper introduces Para-DPMM, a novel method for clustering single-cell RNA sequencing (scRNA-seq) data. It addresses the challenges of improving clustering accuracy, automatically determining the number of clusters, and significantly speeding up computation for massive datasets by employing a parallelized split-merge Markov Chain Monte Carlo (MCMC) approach on a Dirichlet Process Mixture Model (DPMM).

What Problem Does This Paper Address?

The explosion of single-cell RNA sequencing (scRNA-seq) technologies, particularly droplet-based methods, has generated unprecedented amounts of data. Analyzing this data is crucial for understanding cellular heterogeneity and biological processes. However, existing clustering methods face several limitations:

  • Suboptimal Clustering Quality: Current methods often struggle to achieve the highest possible accuracy in identifying distinct cell populations.
  • Need for Prior Knowledge: Many models require users to specify the number of clusters beforehand, which is often unknown for complex biological systems.
  • Computational Bottlenecks: The sheer scale of modern scRNA-seq datasets (millions of cells) makes traditional, computationally intensive clustering algorithms prohibitively slow.
  • Data Characteristics: scRNA-seq data is inherently discrete (UMI counts), and many methods are designed for continuous data, potentially losing information or requiring complex preprocessing.

Methods

The core innovation of this paper is the Para-DPMM (Parallelized Split Merge Sampling on Dirichlet Process Mixture Model). Here's a breakdown of its key components:

  • Dirichlet Process Mixture Model (DPMM): This is the underlying statistical model. DPMMs are powerful because they are non-parametric, meaning they can automatically infer the number of clusters from the data, avoiding the need for prior specification. They model the data using a mixture of distributions, where the Dirichlet process acts as a prior that allows for an infinite number of components (clusters).
  • Split-Merge MCMC: Traditional DPMM inference can be slow and difficult to parallelize. Para-DPMM employs a split-merge Markov Chain Monte Carlo (MCMC) approach. Instead of sampling each data point individually, this method proposes to split existing clusters into new ones or merge existing clusters. This "cluster-level" sampling is more efficient and improves convergence.
  • Parallelization: The split-merge MCMC algorithm is designed for high parallelization. By explicitly instantiating cluster parameters as variables, the method allows for data points to be conditionally independent, enabling them to be processed in parallel across multiple CPU cores on High-Performance Computing (HPC) clusters. This is a significant departure from methods that struggle with inter-data point dependencies.
  • Local Gibbs Sampling for Split Proposals: To ensure that split proposals are reasonable and have a high acceptance rate, the method incorporates local Gibbs sampling within a cluster to identify potential sub-clusters before proposing a split. This helps avoid getting stuck in low-probability regions of the sampling space.

Datasets

The authors evaluated Para-DPMM on several datasets:

  • Small, Medium, and Large-Scale scRNA-seq Datasets: These were derived from T cell populations and used to compare Para-DPMM against existing methods across varying numbers of cells and genes.
  • Fresh PBMC 68K Dataset: A large, publicly available dataset of 68,000 peripheral blood mononuclear cells was used to demonstrate the model's scalability and ability to handle real-world, massive datasets.
  • Pairwise PBMC Cell Type Datasets: Three specific pairs of cell types were isolated to rigorously test the model's ability to distinguish closely related cell populations.

Key Insights and Ideas

  • Cluster-Level Sampling is Key: The split-merge mechanism, operating at the cluster level rather than the data-point level, is the primary driver of improved convergence and optimality. This is a crucial insight for efficient inference in mixture models.
  • Parallelization for Scale: Explicitly modeling cluster parameters unlocks significant parallelization potential, making it feasible to analyze datasets with tens of thousands of cells in minutes.
  • Non-Parametric Advantage: The DPMM's ability to automatically determine the number of clusters is a major advantage, removing a significant user burden and allowing for the discovery of unexpected cellular heterogeneity.
  • Discrete Data Modeling: Directly modeling discrete UMI counts with a multinomial distribution is more natural and avoids potential biases introduced by continuous transformations.

Key Results

  • Improved Clustering Accuracy: Para-DPMM achieved significant improvements in clustering accuracy, with approximately a 7% improvement for small datasets and over 20% improvement for large, challenging datasets compared to state-of-the-art methods like Seurat, CellTree, and DIMM-SC.
  • Faster Computational Speed: The parallelized nature of Para-DPMM leads to substantial speedups. For the large PBMC 68K dataset, it was approximately 12 times faster using 32 cores compared to a single core. It also significantly outperformed other methods in terms of runtime.
  • Scalability: The model demonstrates excellent scalability, performing well on datasets with varying numbers of cells and genes.
  • Robustness: The model showed robustness to hyperparameter choices, with little effect on clustering results when the parameter 'a' varied.

Limitations and Future Work

  • Computational Cost on Small Datasets: For very small datasets, the overhead of parallelization can sometimes lead to slower performance compared to using a few cores. The authors suggest that for such cases, using more than 8 cores might not be beneficial.
  • UMI-Based Data: The model is specifically designed for datasets generated using UMI-based techniques. For older datasets that rely on methods like RPKM or FPKM, other clustering approaches that handle continuous data might be more appropriate.
  • Future Directions: The authors suggest extending Para-DPMM to handle datasets from heterogeneous sources (e.g., multiple individuals) by incorporating hierarchical processes. They also propose exploring semi-supervised guidance when purified cell populations are available to further improve clustering accuracy.

Summary updated

Abstract

Motivation: With the development of droplet based systems, massive single cell transcriptome data has become available, which enables analysis of cellular and molecular processes at single cell resolution and is instrumental to understanding many biological processes. While state-of-the-art clustering methods have been applied to the data, they face challenges in the following aspects: (1) the clustering quality still needs to be improved; (2) most models need prior knowledge on number of clusters, which is not always available; (3) there is a demand for faster computational speed. Results: We propose to tackle these challenges with Para llelized Split Merge Sampling on D irichlet P rocess M ixture M odel (the Para-DPMM model). Unlike classic DPMM methods that perform sampling on each single data point, the split merge mechanism samples on the cluster level, which significantly improves convergence and optimality of the result. The model is highly parallelized and can utilize the computing power of high performance computing (HPC) clusters, enabling massive inference on huge datasets. Experiment results show the model achieves about 7% improvement in clustering accuracy for small datasets and more than 20% improvement for large challenging datasets compared with current widely used models. In the mean time, the model’s computing speed is significantly faster. Availability: Source code is publicly available on https://github.com/tiehangd/Para_DPMM/tree/master/Para_DPMM_package
BibTeX
@misc{duan2018parallelized,
  author = {Tiehang Duan and José Pinto and Xiaohui Xie},
  title = {{Parallelized Inference for Single Cell Transcriptomic Clustering with Split Merge Sampling on DPMM Model}},
  year = {2018},
  doi = {10.1101/271163},
  howpublished = {bioRxiv},
}
Figure