Accelerated parallel algorithm for gene network reverse engineering

Abstract

Background: The Algorithm for the Reconstruction of Accurate Cellular Networks (ARACNE) represents one of the most effective tools to reconstruct gene regulatory networks from large-scale molecular profile datasets. However, previous implementations require intensive computing resources and, in some cases, restrict the number of samples that can be used. These issues can be addressed elegantly in a GPU computing framework, where repeated mathematical computation can be done efficiently, but requires extensive redesign to apply parallel computing techniques to the original serial algorithm, involving detailed optimization efforts based on a deep understanding of both hardware and software architecture.

Result: Here, we present an accelerated parallel implementation of ARACNE (GPU-ARACNE). By taking advantage of multi-level parallelism and the Compute Unified Device Architecture (CUDA) parallel kernel-call library, GPU-ARACNE successfully parallelizes a serial algorithm and simplifies the user experience from multi-step operations to one step. Using public datasets on comparable hardware configurations, we showed that GPU-ARACNE is faster than previous implementations and is able to reconstruct equally valid gene regulatory networks.

Conclusion: Given that previous versions of ARACNE are extremely resource demanding, either in computational time or in hardware investment, GPU-ARACNE is remarkably valuable for researchers who need to build complex regulatory networks from large expression datasets, but with limited budget on computational resources. In addition, our GPU-centered optimization of adaptive partitioning for Mutual Information (MI) estimation provides lessons that are applicable to other domains.

Keywords: CUDA; GPU-ARACNE; Gene expression dataset; Mutual information; Parallel computing; Regulatory networks.

Fig. 1

Adaptive partitioning schema to estimate mutual information. Each blue point represents one gene expression in one sample after ranking. X-axis and Y-axis represent 2 different genes. Boundaries are possible partitioning. Left plot shows the input data, middle plot shows the first partition, right plot shows a second partition

Fig. 2

GPU-ARACNE workflow. Left box represents data/operations on host, and right blue box covers data/operations on GPU device. Arrows represent data flow. In left box, heat-map represents gene expression matrix and permuted matrix

Fig. 3

GPU multi-threading structure schema. a Data/operations on GPU global memory. Dotted boxes represent virtual warps. b In GPU block shared memory, each blue shaded box represents one GPU block. Each curved line represents one thread. c Stored data-structure to compute mutual information for each pair of genes. One node in the tree represents un-normalized MI calculated from one quartz after each partitioning, stored in each block shared memory. d Network after collecting all pairwise mutual information

Fig. 4

GPU-ARACNE speed benchmarking. a GPU-ARACNE-V1 performance. X-axis represents different algorithms/setting. Y-axis represents runtime in seconds. ARACNE runtime is truncated to show ARACNE-AP and GPU-ARACNE-V1 running time. Left plot shows result using 200 breast cancer samples, right plot shows result using 550 prostate cancer samples. b-c GPU-ARACNE-V2 performance. X-axis represents sample size; Y-axis shows the running time in seconds

Fig. 5

Estimated mutual information and networks. a-b Density plot of MI calculated from GPU-ARACNE and ARACNE-AP for breast cancer and prostate cancer dataset, respectively. X-axis represents ARACNE-AP MI; Y-axis represents GPU-ARACNE MI. Each black points represent one pairwise MI in corresponding gene regulatory network. The blue shades correspond to density of points representing pairwise MIs. c-d Subnetwork of breast cancer and prostate cancer gene regulatory network of top 100 most connected transcription factors and their targets

Fig. 6

FoxM1 breast cancer regulon. GPU-ARACNE predicted FoxM1 breast cancer specific regulon, centered by FoxM1 as the transcription factor, connecting to its predicted transcriptional gene targets (other circles). FoxM1 targets were color coded according to the evidence validating their biological relevance. NCBI curated database reported targets were colored as pink ones; Literature reported by experiments were colored as orange ones. All edge length and thickness were weighted by the estimated Mutual information between targets and FoxM1. The closer one target is to FoxM1, the stronger the interaction is