  RNA secondary structure folding kinetics is known to be important for the
biological function of certain processes, such as the hok/sok system in E.
coli. Although linear algebra provides an exact computational solution of
secondary structure folding kinetics with respect to the Turner energy model
for tiny (~ 20 nt) RNA sequences, the folding kinetics for larger sequences can
only be approximated by binning structures into macrostates in a coarse-grained
model, or by repeatedly simulating secondary structure folding with either the
Monte Carlo algorithm or the Gillespie algorithm. Here we investigate the
relation between the Monte Carlo algorithm and the Gillespie algorithm. We
prove that asymptotically, the expected time for a K-step trajectory of the
Monte Carlo algorithm is equal to <N> times that of the Gillespie algorithm,
where <N> denotes the Boltzmann expected network degree. If the network is
regular (i.e. every node has the same degree), then the mean first passage time
(MFPT) computed by the Monte Carlo algorithm is equal to MFPT computed by the
Gillespie algorithm multiplied by <N>; however, this is not true for
non-regular networks. In particular, RNA secondary structure folding kinetics,
as computed by the Monte Carlo algorithm, is not equal to the folding kinetics,
as computed by the Gillespie algorithm, although the mean first passage times
are roughly correlated. Simulation software for RNA secondary structure folding
according to the Monte Carlo and Gille- spie algorithms is publicly available,
as is our software to compute the expected degree of the net- work of secondary
structures of a given RNA sequence { see http://bioinformatics.bc.edu/clote/
RNAexpNumNbors.
