Optimising parallel R correlation matrix calculations on gene expression data using MapReduce

Shicai Wang, Ioannis Pandis, David Johnson, Ibrahim Emam, Florian Guitton, Axel Oehmichen, Yike GuoBMC Bioinformatics 2014 · OpenReview

TL;DR

This paper tackles the computational bottleneck of calculating correlation matrices for large-scale gene expression data, a crucial step in patient stratification. They introduce an optimized MapReduce-based algorithm implemented in R (via RHIPE) that significantly speeds up these calculations, outperforming traditional R and other parallel approaches, especially on massive datasets.

What Problem Does This Paper Address?

Modern biomedical research increasingly relies on high-throughput molecular profiling (like gene expression data) to stratify patients and improve clinical decision-making. A common technique for this is unsupervised clustering, which heavily depends on calculating correlation matrices between subjects based on their molecular profiles. However, as datasets grow exponentially with new sequencing technologies, the performance of existing correlation calculation methods, even parallelized ones, becomes a significant bottleneck. This slowness hinders timely clinical analysis. The authors specifically highlight that in their experience with the tranSMART platform, the R workflow for preparing these matrices is "sub-standard," leading to impractically long computation times for large datasets.

Methods

The core of this paper is the development and evaluation of a parallelized correlation matrix calculation algorithm leveraging the MapReduce framework. Here's a breakdown:

  • MapReduce Fundamentals: The authors explain the basic MapReduce model: Mappers transform input data into key-value pairs, Combiners (optional) sort and pack these pairs, and Reducers aggregate the results. This is applied to distribute the computationally intensive task of pairwise correlation calculations across multiple nodes.
  • Data Distribution: Input data (gene expression profiles for subjects) is divided into blocks. Each block is processed by a Mapper, which then sends it to Reducers.
  • Optimized Correlation Calculation:
    • Redundant Calculation Skipping: The initial approach calculates each correlation twice (e.g., correlation between subject A and B, and then B and A). The authors introduce an optimization where Mappers only send data blocks to Reducers if the block ID is greater than the Reducer ID, ensuring each pair is calculated only once.
  • Load Balancing: The redundancy skipping can lead to imbalanced workloads among Reducers. To address this, they employ a "matrix transformation algorithm" that redistributes the workload, ensuring each Reducer handles a balanced number of calculations. This involves mapping the lower-left triangular section of the correlation matrix to the upper-right.
  • Implementation: The algorithm is implemented using RHIPE, an R package that bridges R with Hadoop's MapReduce capabilities. This allows researchers to use familiar R syntax while benefiting from distributed computing.

Datasets

The authors evaluated their approach using several publicly available gene expression datasets:

  • MULTMYEL: A smaller dataset (559 subjects) used for micro-benchmarking.
  • ONCOLOGY (GSE2109): A larger dataset (2158 subjects) used for macro-benchmarking.
  • LEukemia (GSE13159): Another large dataset (2096 subjects) used for macro-benchmarking.
  • TCGA: A dataset (547 subjects) used for evaluating Kendall correlation, which is particularly computationally expensive.
  • Artificial Datasets: Created by combining ONCOLOGY and LEukemia datasets to simulate even larger scales (4254 and 8508 subjects).

They also mention using the tranSMART platform as their motivation, which integrates various biomedical data.

Key Insights and Ideas

  • Correlation Matrix is the Bottleneck: The paper strongly emphasizes that for many high-dimensional data analysis tasks like clustering, the time-consuming part isn't the clustering algorithm itself, but the preceding correlation matrix calculation. This is a critical insight for optimizing such pipelines.
  • MapReduce for Scientific Computing: While MapReduce is often associated with web-scale data processing, this paper demonstrates its effectiveness and potential for accelerating computationally intensive scientific tasks, particularly in bioinformatics.
  • Balancing Performance and Scalability: The authors highlight the trade-offs between different parallelization strategies. While vanilla R might be fastest for small datasets, it doesn't scale. Optimized parallel methods like Snowfall and RHIPE offer scalability, but RHIPE, with its MapReduce foundation, shows superior performance on truly massive datasets due to efficient data handling.
  • The Power of Data Preparation Optimization: The results show that significant speedups come not just from parallel computation but also from optimizing the data preparation and distribution phase, especially when using distributed file systems like HDFS.

Key Results

The paper presents quantitative results from micro and macro-benchmarks:

  • Micro-benchmark (MULTMYEL dataset):
    • Optimized RHIPE showed a 3.26-5.83 fold increase compared to default Snowfall.
  • Optimized RHIPE was 1.56-1.64 fold faster than basic RHIPE.
  • Vanilla R and optimized Snowfall were faster than optimized RHIPE in this micro-benchmark, but this advantage did not hold for larger datasets.
  • Macro-benchmark (larger datasets):
    • Optimized RHIPE performed 2.03-16.56 times faster than vanilla R.
  • Optimized RHIPE was 1.22-1.71 times faster than optimized Snowfall, largely due to faster data preparation (3.30-5.13 times faster).
  • Kendall Correlation: Both optimized RHIPE and optimized Snowfall completed the Kendall correlation on the TCGA dataset within 7 hours, performing approximately 30 times faster than estimated vanilla R execution times (which were estimated to be days or weeks for larger datasets).

Limitations and Future Work

  • Micro-benchmark Performance: The authors acknowledge that for the micro-benchmark, vanilla R and optimized Snowfall outperformed their optimized RHIPE. This suggests that for smaller datasets, the overhead of MapReduce (e.g., Hadoop job initialization) might outweigh its benefits.
  • Future Work: The authors aim to use this optimized algorithm as a foundation for further optimizing high-throughput molecular data correlation calculations for "Big Data" applications. They propose that the MapReduce framework is highly promising for this domain.

Summary updated

Abstract

High-throughput molecular profiling data has been used to improve clinical decision making by stratifying subjects based on their molecular profiles. Unsupervised clustering algorithms can be used for stratification purposes. However, the current speed of the clustering algorithms cannot meet the requirement of large-scale molecular data due to poor performance of the correlation matrix calculation. With high-throughput sequencing technologies promising to produce even larger datasets per subject, we expect the performance of the state-of-the-art statistical algorithms to be further impacted unless efforts towards optimisation are carried out. MapReduce is a widely used high performance parallel framework that can solve the problem. In this paper, we evaluate the current parallel modes for correlation calculation methods and introduce an efficient data distribution and parallel calculation algorithm based on MapReduce to optimise the correlation calculation. We studied the performance of our algorithm using two gene expression benchmarks. In the micro-benchmark, our implementation using MapReduce, based on the R package RHIPE, demonstrates a 3.26-5.83 fold increase compared to the default Snowfall and 1.56-1.64 fold increase compared to the basic RHIPE in the Euclidean, Pearson and Spearman correlations. Though vanilla R and the optimised Snowfall outperforms our optimised RHIPE in the micro-benchmark, they do not scale well with the macro-benchmark. In the macro-benchmark the optimised RHIPE performs 2.03-16.56 times faster than vanilla R. Benefiting from the 3.30-5.13 times faster data preparation, the optimised RHIPE performs 1.22-1.71 times faster than the optimised Snowfall. Both the optimised RHIPE and the optimised Snowfall successfully performs the Kendall correlation with TCGA dataset within 7 hours. Both of them conduct more than 30 times faster than the estimated vanilla R. The performance evaluation found that the new MapReduce algorithm and its implementation in RHIPE outperforms vanilla R and the conventional parallel algorithms implemented in R Snowfall. We propose that MapReduce framework holds great promise for large molecular data analysis, in particular for high-dimensional genomic data such as that demonstrated in the performance evaluation described in this paper. We aim to use this new algorithm as a basis for optimising high-throughput molecular data correlation calculation for Big Data.
BibTeX
@article{wang2014optimising,
  author = {Shicai Wang and Ioannis Pandis and David Johnson and Ibrahim Emam and Florian Guitton and Axel Oehmichen and Yike Guo},
  title = {{Optimising parallel R correlation matrix calculations on gene expression data using MapReduce}},
  journal = {BMC Bioinformatics},
  year = {2014},
  url = {https://openreview.net/forum?id=Cl2AqxNTGE},
}

Loading related content...

Figure