RNA folding kinetics using Monte Carlo and Gillespie algorithms

Abstract

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 ($\approx$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 $\langle N \rangle$ times that of the Gillespie algorithm, where $\langle N \rangle$ 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 $\langle N \rangle$; 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 Gillespie algorithms is publicly available, as is our software to compute the expected degree of the network of secondary structures of a given RNA sequence—see http://bioinformatics.bc.edu/clote/RNAexpNumNbors.

Appendix

1.1 A Markov chain of RNA secondary structures and detailed balance

In this section, we prove that detailed balance does not hold for the Markov chain $\mathcal {M}_1$ of secondary structures for an RNA sequence, where transition probabilities are defined by Eq. (2). The failure of detailed balance is because for almost any RNA sequence, there are secondary structures x, y that are neighbors of each other, but number N(x) of neighbors of x does not equal the number N(y) of neighbors of y. If every secondary structure of a given RNA sequence has the same number of neighbors, then it is easy to show that the Boltzmann distribution $(\pi _1,\ldots ,\pi _n)$ is the stationary distribution, and a small calculation then shows that detailed balance holds. If different structures have different numbers of neighbors, then the Boltzmann distribution is not in general the stationary distribution. To produce an example where detailed balance fails, we must compute the stationary distribution.

For convenience in following the computation, we first present a simple example using the Nussinov energy model, in which the energy E(s) of a structure is defined to be $-1$ multiplied by the number of base pairs. Historically, the Nussinov algorithm and energy model (Nussinov and Jacobson 1980) predate the Zuker algorithm (Zuker and Stiegler 1981) and Turner energy model (Turner and Mathews 2010).

Example 3

(Detailed balance does not hold for Nussinov energy model) Consider the 6-nt RNA sequence GGGCCC of length 6, which has only four secondary structures, each having N(s) neighbors, given in dot-bracket notation as follows:

• 1. $\bullet \bullet \bullet \bullet \bullet \bullet$: the empty structure $s_1$ with no base pairs and $N(s_1)=3$ neighbors.

• 2. $\,{\texttt {(}}\,\bullet \bullet \bullet \bullet \,{\texttt {)}}\,$: the structure $s_2$ with base pair (1, 6) and $N(s_2)=1$ neighbor.

• 3. $\,{\texttt {(}}\,\bullet \bullet \bullet \,{\texttt {)}}\,\bullet$: the structure $s_3$ with base pair (1, 5) and $N(s_3)=1$ neighbor.

• 4. $\bullet \,{\texttt {(}}\,\bullet \bullet \bullet \,{\texttt {)}}\,$: the structure $s_4$ with base pair (2, 6) and $N(s_4)=1$ neighbor.

The transition probability matrix M is given as follows, where we compute the values to 20 decimal places using Eq. (2), but display only 4 decimal places for notational convenience:

$$\begin{aligned} M&= \left( \begin{array}{llll} 0.0000&{} \quad 0.333\overline{3} &{}\quad 0.333\overline{3} &{}\quad 0.333\overline{3}\\ 0.1974&{} \quad 0.8026&{} \quad 0.0000 &{}\quad 0.0000\\ 0.1974&{}\quad 0.8026&{} \quad 0.0000 &{}\quad 0.0000\\ 0.1974&{} \quad 0.8026&{}\quad 0.0000 &{}\quad 0.0000 \end{array} \right) \end{aligned}$$

(21)

Let $M^{\infty } = \lim \nolimits _{n \rightarrow \infty } M^n$. The stationary probability distribution for M must satisfy $M (p_1^*, p_2^*, p_3^*, p_4^*)^T = (p_1^*, p_2^*, p_3^*, p_4^*)^T$, where T denotes transpose, and so

$$\begin{aligned} M^{\infty }&= \left( \begin{array}{llll} p_1^*&{}\quad p_2^*&{} \quad p_3^* &{}\quad p_4^*\\ p_1^*&{}\quad p_2^*&{}\quad p_3^* &{}\quad p_4^*\\ p_1^*&{}\quad p_2^*&{} \quad p_3^* &{}\quad p_4^*\\ p_1^*&{} \quad p_2^*&{}\quad p_3^* &{}\quad p_4^* \end{array} \right) \end{aligned}$$

Using the actual 20-place values of the transition probability matrix M, whose 4-place approximations are given in Eq. (21), we obtain the millionth power of $M^{(10^6)}$ by a Mathematica computation. The computed 16-place values are shown to 4-place accuracy in the following:

$$\begin{aligned} M^{(10^6)}&= \left( \begin{array}{llll} 0.1648&{} \quad 0.2784&{}\quad 0.2784&{}\quad 0.2784\\ 0.1648&{}\quad 0.2784&{} \quad 0.2784&{}\quad 0.2784\\ 0.1648&{}\quad 0.2784&{} \quad 0.2784&{} \quad 0.2784\\ 0.1648&{}\quad 0.2784&{} \quad 0.2784&{} \quad 0.2784\\ \end{array} \right) \end{aligned}$$

so that the 4-place approximations of the stationary probabilities are as follows: $p_1^* = 0.1648$, $p_2^* = 0.2784$, $p_3^* = 0.2784$, $p_4^* = 0.2784$. We then compute that $p_1^* \cdot p_{1,2} = 0.0550$, while $p_2^* \cdot p_{2,1} = 0.0617$, which shows that detailed balance does not hold.

Using the Turner energy model (Turner and Mathews 2010), the same example yields a different transition probability matrix (not shown), whose millionth power is as follows:

$$\begin{aligned} M^{(10^6)} = \left( \begin{array}{llll} 0.9994655553038468&{} \quad 0.000430085352242845&{}\quad 0.0000521796443227893&{}\quad 0.0000521796443227893\\ 0.9994655553038468&{}\quad 0.000430085352242845&{}\quad 0.0000521796443227893&{} \quad 0.0000521796443227893\\ 0.9994655553038468&{}\quad 0.000430085352242845&{}\quad 0.0000521796443227893&{}\quad 0.0000521796443227893\\ 0.9994655553038468&{}\quad 0.000430085352242845&{}\quad 0.0000521796443227893&{}\quad 0.0000521796443227893 \end{array} \right) \end{aligned}$$

We find that $p_1^* =0.9994655553038468164 \approx 0.9995$, $p_2^* =0.000430315331989701045645180244 \approx 0.0004$, $p_{1,2}=0.001288878388504780024906293256 \approx 0.0013$, $p_{2,1}=0.061737166286699882156163710079 \approx 0.617$, and that $p_1^* \cdot p_{1,2} = 0.0012881895542860573 \approx 0.00129$ while $p_2^* \cdot p_{2,1} = 0.00002656644920676464 \approx 0.00003$. It follows that detailed balance does not hold for the Turner energy model. For RNA sequences of length n, there are exponentially many ($\approx$1.95947 $\cdot n^{-3/2} \cdot 1.86603^n$) secondary structures, so similar computations cannot be carried out, and it may be the case that detailed balance “approximately” holds.