+ Site Statistics
+ Search Articles
+ Subscribe to Site Feeds
Most Shared
PDF Full Text
+ PDF Full Text
Request PDF Full Text
+ Follow Us
Follow on Facebook
Follow on Twitter
Follow on LinkedIn
+ Translate
+ Recently Requested

An implementation of the Gillespie algorithm for RNA kinetics with logarithmic time update

An implementation of the Gillespie algorithm for RNA kinetics with logarithmic time update

Nucleic Acids Research 43(12): 5708-5715

In this paper I outline a fast method called KFOLD for implementing the Gillepie algorithm to stochastically sample the folding kinetics of an RNA molecule at single base-pair resolution. In the same fashion as the KINFOLD algorithm, which also uses the Gillespie algorithm to predict folding kinetics, KFOLD stochastically chooses a new RNA secondary structure state that is accessible from the current state by a single base-pair addition/deletion following the Gillespie procedure. However, unlike KINFOLD, the KFOLD algorithm utilizes the fact that many of the base-pair addition/deletion reactions and their corresponding rates do not change between each step in the algorithm. This allows KFOLD to achieve a substantial speed-up in the time required to compute a prediction of the folding pathway and, for a fixed number of base-pair moves, performs logarithmically with sequence size. This increase in speed opens up the possibility of studying the kinetics of much longer RNA sequences at single base-pair resolution while also allowing for the RNA folding statistics of smaller RNA sequences to be computed much more quickly.

(PDF emailed within 0-6 h: $19.90)

Accession: 057181687

Download citation: RISBibTeXText

PMID: 25990741

DOI: 10.1093/nar/gkv480

Related references

A massively parallel implementation of gillespie algorithm on FPGAs. Conference Proceedings 2008: 1343-1346, 2009

Reaction factoring and bipartite update graphs accelerate the Gillespie Algorithm for large-scale biochemical systems. Plos One 5(1): E8125, 2010

Continuous time Boolean modeling for biological signaling: application of Gillespie algorithm. Bmc Systems Biology 6: 116, 2013

Temporal Gillespie Algorithm: Fast Simulation of Contagion Processes on Time-Varying Networks. Plos Computational Biology 11(10): E1004579, 2016

Simulating the cellular passive transport of glucose using a time-dependent extension of Gillespie algorithm for stochastic pi-calculus. International Journal of Data Mining and Bioinformatics 1(4): 315-336, 2008

An Algorithm with Logarithmic Time Complexity for Interactive Simulation of Hierarchically Articulated Bodies Using a Distributed-memory Architecture. Real-Time Imaging 4(1): 81-96, 1998

The prospectively-reported implementation update and score (PRIUS): a new method for capturing implementation-related developments over time. Bmc Health Services Research 19(1): 124, 2019

Cellular growth and division in the Gillespie algorithm. Systems Biology 1(1): 121-128, 2006

"All possible steps" approach to the accelerated use of Gillespie's algorithm. Journal of Chemical Physics 126(18): 184103, 2007

Modeling Langmuir isotherms with the Gillespie stochastic algorithm. Journal of Chromatography. a 1380: 81-87, 2015

Implementation of automatic external defibrillator using real time ventricular fibrillation detecting algorithm based on time domain analysis. Computer Assisted Surgery 22(Sup1): 86-92, 2017

Modeling ant battles by means of a diffusion-limited Gillespie algorithm. Theoretical Biology Forum 107(1-2): 57-76, 2015

Simulating mesoscopic reaction-diffusion systems using the Gillespie algorithm. Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics 71(4 Pt 1): 041103, 2005

The stochastic evolution of a protocell: the Gillespie algorithm in a dynamically varying volume. Computational and Mathematical Methods in Medicine 2012: 423627, 2012

STOCKS: STOChastic Kinetic Simulations of biochemical systems with Gillespie algorithm. Bioinformatics 18(3): 470-481, 2002