rapidGSEA: Speeding up gene set enrichment analysis on multi-core CPUs and CUDA-enabled GPUs

Christian Hundt, Christian Hundt 0002, Andreas Hildebrandt, Bertil SchmidtBMC Bioinformatics 2016 · DOI

TL;DR

This paper introduces rapidGSEA, a software suite that dramatically accelerates Gene Set Enrichment Analysis (GSEA) by leveraging multi-core CPUs and CUDA-enabled GPUs. By implementing fine-grained parallelization, rapidGSEA achieves speedups of up to two orders of magnitude compared to existing tools, making large-scale GSEA computationally feasible.

What Problem Does This Paper Address?

Gene Set Enrichment Analysis (GSEA) is a crucial bioinformatics technique used to identify biological pathways or gene sets that are significantly associated with observed phenotypes (e.g., disease vs. healthy). The core of GSEA involves calculating an "enrichment score" for each gene set and then determining its statistical significance. This significance is typically assessed through a computationally intensive process called permutation testing, where the phenotype labels of samples are randomly shuffled many times to build a null distribution.

The problem is that this permutation testing is extremely time-consuming, especially when dealing with large datasets (many genes, many patients) and a comprehensive database of gene sets. This computational bottleneck limits the practical application of GSEA for large-scale analyses and complex biological questions. Existing methods for accelerating GSEA have been limited, often relying on cloud computing, which can introduce its own complexities and costs.

Methods

The authors developed rapidGSEA, a software suite comprising two main components:

  • cudaGSEA: This tool is designed for CUDA-enabled GPUs. It employs fine-grained parallelization strategies to distribute the GSEA computation across the thousands of cores available on modern GPUs. Key techniques include:
  • Parallel computation of local deviation measures: Instead of processing genes sequentially, cudaGSEA parallelizes the calculation of gene-wise deviation scores across multiple genes simultaneously. It also optimizes memory access patterns by transposing the data matrix for efficient GPU memory reads.
  • GPU-accelerated sorting: A segmented radix sort primitive from the CUB library is used for efficient gene ranking on the GPU.
  • Parallel enrichment score computation: The running sum statistic for enrichment scores is computed in parallel for multiple gene sets within a thread block.
  • ompGSEA: This tool is optimized for multi-core CPUs and uses coarse-grained parallelization. It splits the set of permutations among available CPU threads, allowing for efficient parallel processing on shared-memory architectures.

Both tools are designed to be highly efficient, with cudaGSEA focusing on maximizing the use of massively parallel GPU architectures and ompGSEA on leveraging multi-core CPUs.

Datasets

The primary dataset used for evaluation was from GEO Series GSE19429, consisting of gene expression data from 183 MDS patients and 17 healthy controls. This dataset was processed to yield 20,639 unique gene symbols. For gene sets, the authors used:

  • The Molecular Signatures Database (MSigDB) v5.1.
  • Specifically, the "Hallmark" collection (50 gene sets) and the "Curated" collection (4,725 gene sets).

The experiments involved testing a wide range of permutations, from 1,024 up to 1,024² (1,048,576) samples.

Key Insights and Ideas

  • GPU Parallelism is Key for Massive Speedups: The most significant speedups are achieved with cudaGSEA on GPUs, demonstrating that the massively parallel nature of GPUs is ideally suited for the highly parallelizable tasks within GSEA.
  • Fine-grained Parallelization is Crucial for GPUs: Unlike CPUs where coarse-grained parallelism (e.g., one thread per permutation) is effective, GPUs require fine-grained strategies to keep their thousands of cores busy. This involves parallelizing individual computational steps like deviation calculation and sorting.
  • CPU Parallelism Still Offers Significant Gains: While not as dramatic as GPU speedups, ompGSEA provides substantial acceleration on multi-core CPUs, making GSEA more accessible even without specialized hardware.
  • Memory Management is Critical on GPUs: The limited RAM on GPUs necessitates careful management of data, including techniques like transposing matrices and using shared memory to avoid slow global memory accesses.
  • Standard GSEA Implementations are a Bottleneck: The comparison with broadGSEA highlights that traditional, less parallelized implementations are a major bottleneck, with their performance scaling poorly with increasing computational demands.

Key Results

  • Dramatic Speedups: rapidGSEA achieves speedups of approximately one order of magnitude on multi-core CPUs (ompGSEA) and up to two orders of magnitude on CUDA-enabled GPUs (cudaGSEA) compared to the established broadGSEA tool.
  • Concrete Performance Example: For a dataset of 20,639 genes and 200 patients, performing 1,048,576 permutations takes approximately 13 days with broadGSEA on a Xeon CPU, but can be reduced to less than one hour on a GeForce Titan X GPU or less than two hours on a Tesla K40c GPU.
  • Accuracy Compliance: The computed enrichment scores from rapidGSEA were found to be highly accurate, matching broadGSEA within six decimal places for both single and double-precision arithmetic. Comparisons of score distributions also showed minimal differences, with Kolmogorov distances typically below 0.0018.
  • Scalability: ompGSEA demonstrated near-linear speedup on CPUs up to ten cores, with hyperthreading providing an efficiency of 98%.

Limitations and Future Work

  • GPU Memory Limitations: While GPUs offer massive parallelism, their limited RAM can be a bottleneck for storing very large numbers of permutations. The authors note that the GeForce Titan X and Tesla K40c can store tens of thousands of permutations, but for extremely large permutation counts, this can become a constraint.
  • Input/Output Overhead: Parsing input files and dumping results to disk takes several seconds and cannot be parallelized on the GPU, representing a fixed overhead.
  • Future Directions:
    • Cluster Computing: The authors suggest extending rapidGSEA to run on compute clusters with multiple GPUs attached to each node for even greater scalability.
  • Extended GSEA Methods: Investigating how the parallelization techniques can be applied to accelerate graph-based (Gene Graph Enrichment Analysis) and network-based (Network-based GSEA) enrichment methods.
  • Further Optimization: Exploring more advanced parallelization techniques for GSEA on distributed memory architectures using Message Passing Interface (MPI).

Summary updated

BibTeX
@article{hundt2016rapidgsea,
  author = {Christian Hundt and Christian Hundt and Andreas Hildebrandt and Bertil Schmidt},
  title = {{rapidGSEA: Speeding up gene set enrichment analysis on multi-core CPUs and CUDA-enabled GPUs}},
  journal = {BMC Bioinformatics},
  year = {2016},
  doi = {10.1186/s12859-016-1244-x},
}
Figure