Abstract: Network properties of the ensemble of RNA structures

A neighbor of the RNA secondary structure s is obtained by removing, adding or shifting a base pair in s. Here, we describe the first efficient algorithm to compute the expected number of neighbors for the collection of all secondary structures of a given RNA sequence. This surprisingly complex algorithm permits a better understanding of kinetics of RNA folding when allowing defect diffusion, helix zippering, and related conformation transformations. Moreover, only when allowing shift moves does the network of secondary structures for certain RNAs satisfy the requirements of a small-world network. RNA secondary structure kinetics is plays an essential role in certain biological processes, such as the hok/sok host-killing/suppression of killing (hok/sok) system that kills E. coli replicates if insufficient plasmids are transfered to the new daughter cell Nevertheless, RNA folding kinetics remains a difficult problem, since it is known that computation of optimal folding pathways is NP-complete [3]. Due to the biological importance of RNA folding kinetics, users generally run a secondary structure kinetics program, such as Kinfold, Kinefold, RNAKinetics. However, repeated simulations must be per-formed, each requiring lengthy computation times – for instance, the population occupancy curve for yeast phe-tRNA required 3 months of CPU time on a 2.4 GHz Intel Pentium 4 running linux [4]). Coarse-graine