Adaptive tree-based search for Stochastic simulation algorithm

Vo Hong Thanh*, Roberto Zunino

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

17 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)341-357
Number of pages17
JournalInternational Journal of Computational Biology and Drug Design
Volume7
Issue number4
DOIs
Publication statusPublished - 2014
MoE publication typeA1 Journal article-refereed

Keywords

  • proteome, algorithm
  • animal
  • automated pattern recognition
  • biological model
  • computer simulation
  • human
  • metabolism
  • physiology
  • procedures
  • signal transduction
  • statistical analysis
  • statistical model
  • statistics, Algorithms
  • Animals
  • Computer Simulation
  • Data Interpretation, Statistical
  • Humans
  • Models, Biological
  • Models, Statistical
  • Pattern Recognition, Automated
  • Proteome
  • Signal Transduction
  • Stochastic Processes

Fingerprint Dive into the research topics of 'Adaptive tree-based search for Stochastic simulation algorithm'. Together they form a unique fingerprint.

Cite this