Webserver for Expected number of structural neighbors

RNAexpNumNbors is a web server that computes the expected degree of the network of RNA secondary structures of a given RNA -- i.e. the expected number of neighbors taken over all secondary structures. Here, we consider two move sets: MS1 and MS2. A neighbor of structure S with respect to MS1 is a structure T obtained by adding or removing a single base pair, whereas a neighbor of structure S with respect to MS2 is a structure T obtained by adding, removing or shifting a single base pair. In addition to programs to compute the expected degree, we also provide a program that implements kinetic folding with respect to MS1 using either the Gillespie algorithm or the Monte Carlo algorithm -- two related methods used in the literature to approximate the mean first passage time (MFPT) -- however, the paper [3] below shows the precise relation between the Gillespie algorithm and the Monte Carlo algorithm and that MFPT computed by each method is quite different.


If you use our program or this server for your work, would you please cite:

  1. Clote P. Expected degree of RNA secondary structure networks. J Comput Chem. 2015 Jan 15;36(2):103-17. doi: 10.1002/jcc.23776. Epub 2014 Nov 7
  2. P. Clote, A. Bayegan. Network properties of the ensemble of RNA structures. PLoS One. 2015 Oct 21;10(10):e0139476. doi: 10.1371/journal.pone.0139476
  3. P. Clote, A. Bayegan. RNA folding kinetics using Monte Carlo and Gillespie algorithms. J Math Biol, in press (2017), arXiv article ID 1707.03922.
The article [1] describes dynamic programming algorithms to compute the expected network degree (expected number of neighbors) for the directed graph G = (V,E) , where V is the set of all secondary structures of a given RNA sequence, and E is the set of directed edges s → t, where structure t is obtained from s by an element of move set MS1 consisting of base pair additions and removals. The article [2] describes a surprisingly complex extension of the algorithm [1] to compute the expected network degree (expected number of neighbors) for the directed graph G = (V,E) , where V is the set of all secondary structures of a given RNA sequence, and E is the set of directed edges s → t, where structure t is obtained from s by an element of move set MS2 consisting of base pair additions, removals, and shifts. Finally article [3] concerns the relation between computing mean first passage time (MFPT) of RNA secondary structure folding when using the Gillespie algorithm (simulation of a continuous time Markov process) versus using the Monte Carlo algorithm (simulation of a discrete time Markov chain).