Efficient constant-time complexity algorithm for stochastic simulation of large reaction networks

Research output: Contribution to journalArticleScientificpeer-review

Standard

Efficient constant-time complexity algorithm for stochastic simulation of large reaction networks. / Thanh, V.H.; Zunino, R.; Priami, C.

In: IEEE/ACM Transactions on Computational Biology and Bioinformatics, Vol. 14, No. 3, 2017, p. 657-667.

Research output: Contribution to journalArticleScientificpeer-review

Harvard

APA

Vancouver

Author

Bibtex - Download

@article{41ee7b8f80df4ba9ba4261ccd11e1179,
title = "Efficient constant-time complexity algorithm for stochastic simulation of large reaction networks",
abstract = "Exact stochastic simulation is an indispensable tool for a quantitative study of biochemical reaction networks. The simulation realizes the time evolution of the model by randomly choosing a reaction to fire and update the system state according to a probability that is proportional to the reaction propensity. Two computationally expensive tasks in simulating large biochemical networks are the selection of next reaction firings and the update of reaction propensities due to state changes. We present in this work a new exact algorithm to optimize both of these simulation bottlenecks. Our algorithm employs the composition-rejection on the propensity bounds of reactions to select the next reaction firing. The selection of next reaction firings is independent of the number reactions while the update of propensities is skipped and performed only when necessary. It therefore provides a favorable scaling for the computational complexity in simulating large reaction networks. We benchmark our new algorithm with the state of the art algorithms available in literature to demonstrate its applicability and efficiency. {\circledC} 2004-2012 IEEE.",
keywords = "Biology, Complex networks, Stochastic models, Stochastic systems, Biochemical network, Biochemical reaction network, Computational biology, Constant time complexity, Indispensable tools, State-of-the-art algorithms, Stochastic simulation algorithms, Stochastic simulations, Computational complexity, algorithm, biological model, biology, computer simulation, Markov chain, procedures, time factor, Algorithms, Computational Biology, Computer Simulation, Models, Biological, Stochastic Processes, Time Factors",
author = "V.H. Thanh and R. Zunino and C. Priami",
note = "cited By 10",
year = "2017",
doi = "10.1109/TCBB.2016.2530066",
language = "English",
volume = "14",
pages = "657--667",
journal = "IEEE/ACM Transactions on Computational Biology and Bioinformatics",
issn = "1326-1337",
publisher = "Institute of Electrical and Electronics Engineers",
number = "3",

}

RIS - Download

TY - JOUR

T1 - Efficient constant-time complexity algorithm for stochastic simulation of large reaction networks

AU - Thanh, V.H.

AU - Zunino, R.

AU - Priami, C.

N1 - cited By 10

PY - 2017

Y1 - 2017

N2 - Exact stochastic simulation is an indispensable tool for a quantitative study of biochemical reaction networks. The simulation realizes the time evolution of the model by randomly choosing a reaction to fire and update the system state according to a probability that is proportional to the reaction propensity. Two computationally expensive tasks in simulating large biochemical networks are the selection of next reaction firings and the update of reaction propensities due to state changes. We present in this work a new exact algorithm to optimize both of these simulation bottlenecks. Our algorithm employs the composition-rejection on the propensity bounds of reactions to select the next reaction firing. The selection of next reaction firings is independent of the number reactions while the update of propensities is skipped and performed only when necessary. It therefore provides a favorable scaling for the computational complexity in simulating large reaction networks. We benchmark our new algorithm with the state of the art algorithms available in literature to demonstrate its applicability and efficiency. © 2004-2012 IEEE.

AB - Exact stochastic simulation is an indispensable tool for a quantitative study of biochemical reaction networks. The simulation realizes the time evolution of the model by randomly choosing a reaction to fire and update the system state according to a probability that is proportional to the reaction propensity. Two computationally expensive tasks in simulating large biochemical networks are the selection of next reaction firings and the update of reaction propensities due to state changes. We present in this work a new exact algorithm to optimize both of these simulation bottlenecks. Our algorithm employs the composition-rejection on the propensity bounds of reactions to select the next reaction firing. The selection of next reaction firings is independent of the number reactions while the update of propensities is skipped and performed only when necessary. It therefore provides a favorable scaling for the computational complexity in simulating large reaction networks. We benchmark our new algorithm with the state of the art algorithms available in literature to demonstrate its applicability and efficiency. © 2004-2012 IEEE.

KW - Biology

KW - Complex networks

KW - Stochastic models

KW - Stochastic systems, Biochemical network

KW - Biochemical reaction network

KW - Computational biology

KW - Constant time complexity

KW - Indispensable tools

KW - State-of-the-art algorithms

KW - Stochastic simulation algorithms

KW - Stochastic simulations, Computational complexity, algorithm

KW - biological model

KW - biology

KW - computer simulation

KW - Markov chain

KW - procedures

KW - time factor, Algorithms

KW - Computational Biology

KW - Computer Simulation

KW - Models, Biological

KW - Stochastic Processes

KW - Time Factors

U2 - 10.1109/TCBB.2016.2530066

DO - 10.1109/TCBB.2016.2530066

M3 - Article

VL - 14

SP - 657

EP - 667

JO - IEEE/ACM Transactions on Computational Biology and Bioinformatics

JF - IEEE/ACM Transactions on Computational Biology and Bioinformatics

SN - 1326-1337

IS - 3

ER -

ID: 27839854