An implementation of the Gillespie algorithm for RNA kinetics with logarithmic time update. Issue 12 (18th May 2015)

• Record Type: Journal Article
• Authors: Dykeman, Eric C.
• Is Part Of: Nucleic acids research. Volume 43:Issue 12(2015)
• Page Start: 5708
• Page End: 5715
• Publication Date: 2015-05-18
• Subjects: Nucleic acids -- Periodicals; Molecular biology -- Periodicals; 572.805
• DOI: 10.1093/nar/gkv480
• Languages: English
• ISSNs: 0305-1048

Abstract

Abstract: 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.