title: An implementation of the Gillespie algorithm for RNA kinetics with logarithmic time update.
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.
authors.affiliation: York Centre for Complex Systems Analysis, Department of Mathematics and Biology University of York, Deramore Lane, York, YO10 5GE, UK eric.dykeman@york.ac.uk.
authors.forename: Eric C
authors.initials: EC
authors.lastname: Dykeman
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D019295:Computational Biology / Q000379:methods; D007700:Kinetics; D012313:RNA / Q000737:chemistry; D059370:RNA Folding; D016053:RNA, Protozoan / Q000737:chemistry; D014351:Trypanosomatina / Q000235:genetics
chemical_list: D016053:RNA, Protozoan; D012313:RNA