Journal
JOURNAL OF COMPUTATIONAL BIOLOGY
Volume 16, Issue 3, Pages 501-522Publisher
MARY ANN LIEBERT, INC
DOI: 10.1089/cmb.2008.0063
Keywords
tau-leaping; computational complexity; stochastic processes; robustness
Categories
Funding
- NSF [0523761]
- NIMH [MH19138-15]
- Direct For Computer & Info Scie & Enginr
- Division of Computing and Communication Foundations [0523761] Funding Source: National Science Foundation
Ask authors/readers for more resources
The behavior of some stochastic chemical reaction networks is largely unaffected by slight inaccuracies in reaction rates. We formalize the robustness of state probabilities to reaction rate deviations, and describe a formal connection between robustness and efficiency of simulation. Without robustness guarantees, stochastic simulation seems to require computational time proportional to the total number of reaction events. Even if the concentration ( molecular count per volume) stays bounded, the number of reaction events can be linear in the duration of simulated time and total molecular count. We show that the behavior of robust systems can be predicted such that the computational work scales linearly with the duration of simulated time and concentration, and only polylogarithmically in the total molecular count. Thus our asymptotic analysis captures the dramatic speedup when molecular counts are large, and shows that for bounded concentrations the computation time is essentially invariant with molecular count. Finally, by noticing that even robust stochastic chemical reaction networks are capable of embedding complex computational problems, we argue that the linear dependence on simulated time and concentration is likely optimal.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available