Documentation for RNALOSS

If use the RNALOSS web server in your work, then please cite:

[1] "An efficient algorithm to compute the landscape of locally optimal RNA secondary structures with respect to the Nussinov-Jacobson energy model", by P. Clote, Journal of Computational Biology, 12(1) 2005 83--101.

Usage

For the purpose of this web server, an RNA nucleotide sequence is a sequence of characters from the set

{ A,C,G,U,T,a,c,g,u,t }

with no intervening white space or other characters. An RNA nucleotide sequence may be input by (A) file upload, or (B) typing/pasting in a sequence in the appropriate part of the form. In the case of a file upload, the user must indicate the machine (Unix/Windows/Mac) from which the file upload is made, since each operating system has a different end of line character. Uploaded files must be in FASTA format, optionally consisting of a FASTA comment, followed by one or more lines of RNA nucleotides.

Currently there is a 100 nt. upper bound for RNA sequence length. For sequences of length 60 or more, the output is sent by email to the user.

Introduction

In [4] Workman and Krogh showed that mRNA does not have lower folding energy than that of random RNA of the same dinucleotide frequency. Following the methods of [4], Clote et al. [3] showed that a number of structural RNAs have significantly lower folding energy than random RNA of the same dinucleotide frequency. It thus appears that certain structural RNAs have been under selective pressure to have a low folding energy. Is it the case that RNA has also been under selective pressure to fold rapidly, in the sense that the landscape of possible secondary structures has certain properties which permit rapid folding?

In [1] Clote explored an aspect of the folding landscape of RNA, by computing for each k, the number of k-locally optimal secondary structures for a given RNA sequence. Here, a secondary structure is k-locally optimal if it has k fewer base pairs than that of the Nussinov-Jacobson optimal structure, yet no base pairs can be added without violation of the definition of secondary structure (e.g. without adding a pseudoknot) -- see example given below.

The web server RNALOSS implements a new algorithm, described in [1], running in O(n⁴) time and O(n³) space, which computes for a given RNA sequence a₁,...,a_n and all k, the number of k-suboptimal secondary structures on a₁,...,a_n. The resulting density of states histogram for structurally important RNAs (hammerhead ribozymes, micro-RNAs, SECIS elements, etc.) shows a significant difference with that of RNAs of the same dinucleotide frequency, indicating more likely kinetic entrapment of random RNA.

The web server RNALOSS displays tables for the number of secondary structures, the relative density of states, and minimum free energies of sample k-locally optimal secondary structures. The computation of minimum free energy is performed using RNAeval from the Vienna RNA Package.

Example of k-locally optimal secondary structures

To clarify the notion of k-locally optimal secondary structure, we consider the toy example GGGGCCCCC. The maximum number of basepairs is 3; this assumes that there must be at least 3 unpaired bases in a hairpin loop (standard assumption). There is one 0-locally optimal structure (with 3 basepairs) given by (((...))). There are 12 1-locally optimal structures, given by

GGGGCCCCC
..((...))
.(.(...))
.((....))
((...)..)
(..(...))
.((...).)
(.(....))
(.(...)). 
((....).)
((....)).
((...).).
((...))..

Finally, there are three 2-locally optimal secondary structures for GGGGCCCCC, given by

GGGGCCCCC
(...)....
(....)...
...(....)

References

"An efficient algorithm to compute the landscape of locally optimal RNA secondary structures with respect to the Nussinov-Jacobson energy model", P. Clote, Journal of Computational Biology, 12(1) 2005 83--101.
Computational Molecular Biology: An Introduction, P. Clote and R. Backofen, John Wiley & Sons, Ltd., 286 pages, ISBN 0-471-87251-2 (hardback), ISBN 0-471-87252-0 (paperback) August 2000.
"Structural RNA has lower folding energy than random RNA of the same dinucleotide frequency", P. Clote, F. Ferre, E. Kranakis, D. Krizanc, RNA (in press).
"No evidence that mRNAs have lower folding free energies than random sequences with the same dinucleotide distribution", C. Workman and A. Krogh, Nucleic Acids Res. 27 1999 4816--4822,