Journal Papers Adaptive Tree-Based Search for Stochastic Simulation Algorithm


Stochastic modelling and simulation is a well-known approach to predicting the behaviour of biochemical systems. Its main applications lie in those systems in which the inherently random fluctuations of some chemical species are significant, as often is the case whenever just a few macromolecules can have a large effect on the rest of the system. The stochastic simulation algorithm (SSA), which was introduced by Gillespie, is a standard method to properly realize the stochastic nature of reactions. A large effort is then ongoing to improve the performance of SSA so to make it possible to simulate larger models. In this paper we propose an improvement to the 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 chemical reactions to be fired, moving from linear time complexity to logarithmic complexity. We combine this idea with others from the literature, and compare the performance of our algorithm with previous ones. Our experiments show that our algorithm is faster, especially on large models.

Paper Details


T. Vo,  R. Zunino


Intl. J. of Computational Biology and Drug Design, 7, , 341-57