GPU-accelerated steady-state computation of large probabilistic Boolean networks

Andrzej Mizera, Jun Pang*, Qixia Yuan

*Corresponding author for this work

Research output: Contribution to journalArticleResearchpeer-review

1 Citation (Scopus)

Abstract

Computation of steady-state probabilities is an important aspect of analysing biological systems modelled as probabilistic Boolean networks (PBNs). For small PBNs, efficient numerical methods to compute steady-state probabilities of PBNs exist, based on the Markov chain state-transition matrix. However, for large PBNs, numerical methods suffer from the state-space explosion problem since the state-space size is exponential in the number of nodes in a PBN. In fact, the use of statistical methods and Monte Carlo methods remain the only feasible approach to address the problem for large PBNs. Such methods usually rely on long simulations of a PBN. Since slow simulation can impede the analysis, the efficiency of the simulation procedure becomes critical. Intuitively, parallelising the simulation process is the ideal way to accelerate the computation. Recent developments of general purpose graphics processing units (GPUs) provide possibilities to massively parallelise the simulation process. In this work, we propose a trajectory-level parallelisation framework to accelerate the computation of steady-state probabilities in large PBNs with the use of GPUs. To maximise the computation efficiency on a GPU, we develop a dynamical data arrangement mechanism for handling different size PBNs with a GPU. Specially, we propose a reorder-and-split method to handle both large and dense PBNs. Besides, we develop a specific way of storing predictor functions of a PBN and the state of the PBN in the GPU memory. Moreover, we introduce a strongly connected component (SCC)-based network reduction technique to further accelerate the computation speed. Experimental results show that our GPU-based parallelisation gains approximately a 600-fold speedup for a real-life PBN compared to the state-of-the-art sequential method.

Original languageEnglish
Pages (from-to)27-46
Number of pages20
JournalFormal Aspects of Computing
Volume31
Issue number1
DOIs
Publication statusPublished - 12 Feb 2019

Keywords

  • Biological networks
  • Computational modelling
  • Discrete-time Markov chains
  • Graphics processing unit (GPU)
  • Probabilistic Boolean networks
  • Simulation
  • Statistical methods

Fingerprint

Dive into the research topics of 'GPU-accelerated steady-state computation of large probabilistic Boolean networks'. Together they form a unique fingerprint.

Cite this