Fast parallel markov clustering in bioinformatics using massively parallel computing on GPU with CUDA and ELLPACK-R sparse format

Alhadi B., Kevin Burrage, Nicholas A. Hamilton

Research output: Contribution to journalArticlepeer-review

30 Citations (Scopus)

Abstract

Markov clustering (MCL) is becoming a key algorithm within bioinformatics for determining clusters in networks. However, with increasing vast amount of data on biological networks, performance and scalability issues are becoming a critical limiting factor in applications. Meanwhile, GPU computing, which uses CUDA tool for implementing a massively parallel computing environment in the GPU card, is becoming a very powerful, efficient, and low-cost option to achieve substantial performance gains over CPU approaches. The use of on-chip memory on the GPU is efficiently lowering the latency time, thus, circumventing a major issue in other parallel computing environments, such as MPI. We introduce a very fast Markov clustering algorithm using CUDA (CUDA-MCL) to perform parallel sparse matrix-matrix computations and parallel sparse Markov matrix normalizations, which are at the heart of MCL. We utilized ELLPACK-R sparse format to allow the effective and fine-grain massively parallel processing to cope with the sparse nature of interaction networks data sets in bioinformatics applications. As the results show, CUDA-MCL is significantly faster than the original MCL running on CPU. Thus, large-scale parallel computation on off-the-shelf desktop-machines, that were previously only possible on supercomputing architectures, can significantly change the way bioinformaticians and biologists deal with their data.

Original languageEnglish
Article number7
Pages (from-to)679-692
Number of pages14
JournalIEEE/ACM Transactions on Computational Biology and Bioinformatics
Volume9
Issue number3
DOIs
Publication statusPublished - 9 Apr 2012

Keywords

  • CUDA
  • ELLPACK-R sparse format
  • GPU computing
  • Markov clustering
  • PPI networks
  • bioinformatics
  • graphs and networks
  • parallelism and concurrency
  • performance evaluation
  • scalable parallel programming

Fingerprint Dive into the research topics of 'Fast parallel markov clustering in bioinformatics using massively parallel computing on GPU with CUDA and ELLPACK-R sparse format'. Together they form a unique fingerprint.

Cite this