Title: Adaptive tree-based search for stochastic simulation algorithm

Authors: Vo Hong Thanh; Roberto Zunino

Addresses: Department of Information Engineering and Computer Science, University of Trento, Italy ' Department of Mathematics, University of Trento, Italy and COSBI, Italy

Abstract: Stochastic modelling and simulation is a well-known approach for predicting the behaviour of biochemical systems. Its main applications lie in those systems wherein the inherently random fluctuations of some species are significant, as often is the case whenever just a few macromolecules have a large effect on the rest of the system. The Gillespie's stochastic simulation algorithm (SSA) is a standard method to properly realise the stochastic nature of reactions. In this paper we propose an improvement to SSA based on the Huffman tree, a binary tree which is used to define an optimal data compression algorithm. We exploit results from that area to devise an efficient search for next reactions, moving from linear time complexity to logarithmic complexity. We combine this idea with others from literature, and compare the performance of our algorithm with previous ones. Our experiments show that our algorithm is faster, especially on large models.

Keywords: systems biology; biological simulation; SSA; stochastic simulation algorithm; tree search SSA; Huffman tree SSA; stochastic modelling; Gillespie; optimal data compression; biochemical systems; behaviour prediction; random fluctuations.

DOI: 10.1504/IJCBDD.2014.066542

International Journal of Computational Biology and Drug Design, 2014 Vol.7 No.4, pp.341 - 357

Received: 30 Apr 2013
Accepted: 12 Jan 2014
Published online: 25 Apr 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article