Thanh Vo Hong, Zunino Roberto
Department of Information Engineering and Computer Science, University of Trento, Italy.
Department of Mathematics, University of Trento, Italy and COSBI, Italy.
Int J Comput Biol Drug Des. 2014;7(4):341-57. doi: 10.1504/IJCBDD.2014.066542. Epub 2014 Dec 25.
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.
随机建模与模拟是预测生化系统行为的一种知名方法。其主要应用于某些物种的固有随机波动显著的系统，每当少数大分子对系统其余部分有很大影响时，通常就是这种情况。吉莱斯皮随机模拟算法（SSA）是正确实现反应随机性质的标准方法。在本文中，我们基于哈夫曼树提出了对SSA的一种改进，哈夫曼树是一种用于定义最优数据压缩算法的二叉树。我们利用该领域的成果来设计一种高效的下一个反应搜索方法，将线性时间复杂度提升至对数复杂度。我们将这一想法与文献中的其他想法相结合，并将我们算法的性能与之前的算法进行比较。我们的实验表明，我们的算法更快，尤其是在大型模型上。
