A novel parallel Markov clustering method in biological interaction network analysis under multi-GPU computing environment

The various clustering methods are widely applied in analyzing biological interaction networks, such as the protein–protein interaction and the genetic interaction networks. With the rapid growth of these biological datasets in scale, much longer runtime is required to make cluster analyses on them. In this paper, we propose a novel parallel Markov clustering (MCL) method based on the ELLPACK-R sparse matrix format that can run on multiple graphic processing units (GPUs) equipped standalone computers. The method is implemented using the Compute Unified Device Architecture (CUDA) programming framework, and fine-grained warp-level optimization is introduced for improving the performance. The BioGRID, a large-scale and freely accessible database of protein and genetic interactions, is adopted as the dataset in the experiment. The method has been assessed on a desktop computer equipped with two NVIDIA GTX 1070 GPUs. The results show that the proposed multi-GPU method can conduct MCL clustering on the full-size BioGRID database with about 6.5 min, that is much faster than the CPU serial MCL implementation which needs almost an hour and a half execution time.