Skip Navigation


Nucleic Acids Research Advance Access originally published online on May 25, 2007
Nucleic Acids Research 2007 35(Web Server issue):W305-W309; doi:10.1093/nar/gkm255
This Article
Right arrow Abstract Freely available
Right arrow Print PDF (1707K) Freely available
Right arrow Screen PDF (273K) Freely available
Right arrowOA All Versions of this Article:
35/suppl_2/W305    most recent
gkm255v1
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in PubMed
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrow Commercial Re-use Guidelines
for Open Access NAR Content
Google Scholar
Right arrow Articles by Freyhult, E.
Right arrow Articles by Clote, P.
Right arrow Search for Related Content
PubMed
Right arrow PubMed Citation
Right arrow Articles by Freyhult, E.
Right arrow Articles by Clote, P.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Nucleic Acids Research, 2007, Vol. 35, No. suppl_2 W305-W309
© 2007 The Author(s)
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/2.0/uk/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.

Articles

RNAbor: a web server for RNA structural neighbors

Eva Freyhult1, Vincent Moulton2 and Peter Clote3,*

1Linnaeus Centre for Bioinformatics, Uppsala University, 75124 Uppsala, Sweden, 2School of Computing Sciences, University of East Anglia, Norwich, NR4 7TJ, UK and 3Department of Biology, Boston College, Chestnut Hill, MA 02467, USA

*To whom correspondence should be addressed. Tel: + 1 617 552 1332; Fax: + 1 617 552 2011; Email: clote{at}bc.edu

Received January 24, 2007. Revised March 26, 2007. Accepted April 8, 2007.


   ABSTRACT
TOP
 ABSTRACT
INTRODUCTION
 MATERIALS AND METHODS
 RESULTS
 EXAMPLES
 DISCUSSION
 REFERENCES
 
RNAbor provides a new tool for researchers in the biological and related sciences to explore important aspects of RNA secondary structure and folding pathways. RNAbor computes statistics concerning {delta}-neighbors of a given input RNA sequence and structure (the structure can, for example, be the minimum free energy (MFE) structure). A {delta}-neighbor is a structure that differs from the input structure by exactly {delta} base pairs, that is, it can be obtained from the input structure by adding and/or removing exactly {delta} base pairs. For each distance {delta} RNAbor computes the density of {delta}-neighbors, the number of {delta}-neighbors, and the MFE structure, or MFE {delta} structure, among all {delta}-neighbors. RNAbor can be used to study possible folding pathways, to determine alternate low-energy structures, to predict potential nucleation sites and to explore structural neighbors of an intermediate, biologically active structure. The web server is available at http://bioinformatics.bc.edu/clotelab/RNAbor.


   INTRODUCTION
TOP
 ABSTRACT
 INTRODUCTION
MATERIALS AND METHODS
 RESULTS
 EXAMPLES
 DISCUSSION
 REFERENCES
 
RNA plays a surprising and previously unsuspected role in many biological processes, such as post-transcriptional regulation, conformational switches, expansion of the genetic code (such as selenocysteine insertion), ribosomal frameshift, metabolite-binding and chemical modification of specific nucleotides in the ribosome. Apart from its catalytic role as a ribonucleic enzyme (ribozyme) (1), RNA can regulate genes in several ways. For example, by hybridizing to a portion of messenger RNA, small ~ 22 nt RNA molecules perform post-transcriptional gene regulation by RNA interference (RNAi), a process so important that for its discovery the 2006 Nobel Prize in Physiology or Medicine was awarded to A. Z. Fire and C. C. Mello. In addition, by very different means, RNA can perform transcriptional and translational gene regulation by allostery, where a portion of the 5' untranslated region (5' UTR) of mRNA, known as a riboswitch (2,3), undergoes a conformational change upon binding a specific ligand such as adenine, guanine or lysine.

As the field of RNomics matures, many sophisticated computational tools, e.g. RNA structure prediction, alignment and gene finding, have been developed—see (4,5) for recent overviews. Recently developed programs that are of most relevance here include the program Sfold (6,7), that computes a low energy ensemble of structures by sampling from the partition function (8), and an earlier program RNAsubopt (9) that computes all suboptimal structures within a user-specified number of kcal/mol of the minimum free energy (MFE). In addition, the program RNAshapes (10–12) provides a useful description of RNA branching structure by computing the Boltzmann probability of various shapes and also the MFE structure for various shapes. Here, an RNA shape is an equivalence class of secondary structures, describing the overall branching; for instance the shape of a typical cloverleaf tRNA would be [ [ ] [ ] [ ] ].

In this article, we describe the web server RNAbor, which computes the Boltzmann probability and MFE structures which differ by {delta} base pairs from a given initial structure. Unlike most of the tools just described, which focus on the MFE structure or a low energy ensemble, RNAbor yields information concerning the secondary structure folding landscape. Potential applications of RNAbor include the design of RNA aptamers (see (13) for a suggestion how RNA might be designed to inhibit the function of the viral enzymes such as HIV-1 reverse transcriptase and hepatitis C NS3 protease), detection of conformational switches, understanding the role played by biologically active structural intermediates and improvement in secondary structure prediction.


   MATERIALS AND METHODS
TOP
 ABSTRACT
 INTRODUCTION
 MATERIALS AND METHODS
RESULTS
 EXAMPLES
 DISCUSSION
 REFERENCES
 
Let Formula denote a given RNA nucleotide sequence, and let Formula be any given secondary structure of Formula . The structure Formula could be the MFE structure of Formula , it could be the secondary structure obtained from the 3-dimensional X-ray conformation or by comparative sequence analysis, or it could be an arbitrary intermediate structure of particular biological significance. For an integer {delta}, a secondary structure Formula of Formula is a {delta}-neighbor of Formula , if Formula and Formula differ by exactly {delta} base pairs [14]. In (Freyhult, E., Moulton, V. and Clote, P. Boltzmann probability of RNA structural neighbors and riboswitch detection, submitted for publication), we describe new algorithms, which compute the number N{delta} of {delta}-neighbors, the partition function Z{delta} for {delta}-neighbors and the MFE{delta}, and the corresponding MFE{delta} structure over all {delta}-neighbors of a fixed structure Formula .

Computing structural neighbors
To give the reader a feeling for how the algorithms work, we present the recurrence relations to compute the number N{delta} of {delta}-neighbors of Formula . Let Formula . If Formula denotes the number of {delta}-neighbors of the substructure S [i,j], the restriction of Formula to interval [i,j] of Formula , then the number of {delta}-neighbors of Formula , Formula , can be computed by the following recursion:

Formula 1 (1)
where Formula (i.e. the set of Watson-Crick base pairs together with wobbles), b0 = 1 if j is base-paired in S [i,j] and 0 otherwise and b is the base pair distance between S [i,j] and a structure on the same interval [i,j] where a base pair between k and j has been added (taking into account all the base pairs in S [i,j] that need to be broken to allow the addition of this base pair).

This approach for computing N{delta} can be extended to compute the partition function contribution, Z{delta}, of the set of {delta}-neighbors and also to compute the MFE{delta} and the MFE{delta} structure. Computations are made with respect to the Turner energy model (15,16); treatment of the dangle is similar to that in Vienna RNA Package (option -d2). The algorithms employ dynamic programming, and run in O({Delta} · n3) time and O({Delta} · n2) space, where n is the sequence length and {Delta} is the maximum value of {delta}. Since {Delta} can be at most n, the run time cannot be worse than O(n4) and space no worse that O(n3), even if the user does not specify a value of {Delta}. Full details of the algorithms are given in (Freyhult, E., Moulton, V. and Clote, P. Boltzmann probability of RNA structural neighbors and riboswitch detection, submitted for publication).

Web server
The web server available at http://bioinformatics.bc.edu/clotelab/RNAbor runs on a Linux cluster with 20 computational nodes, each with double processors of between 1300 and 3000 MHz and 2 GB RAM (6 Dell PowerEdge 1650, 2 x 1300 MHz Pentium III, 2 GB RAM; 11 Dell PowerEdge 1850, 2 x 2800 + MHz Xeon EM64T, 2 GB RAM; 5 Dell PowerEdge 1850, 2 x 3000 MHz Xeon EM64T, 2 GB RAM).


   RESULTS
TOP
 ABSTRACT
 INTRODUCTION
 MATERIALS AND METHODS
 RESULTS
EXAMPLES
 DISCUSSION
 REFERENCES
 
Due to the time and space constraints of the algorithm, RNA sequences may be of length up to 300 nucleotides. Sequences of length up to 60 are processed interactively and output is displayed in the user's browser window. For sequences of length 61–300, the computation is done off-line and the results are returned to the user by email; for this, the email address is required. The user can either paste an input sequence (with optional secondary structure), or upload a file of the same. The full input consists of up to four lines, illustrated by the following example.Formula The temperature is set to a default value of 37{circ} C; however the user can enter any integer temperature between 0 and 100.

The only required input is an RNA sequence Formula of length at most 300 nucleotides; the FASTA comment, initial secondary structure Formula and upper bound {Delta} are optional inputs. If no secondary structure is given, then the initial structure Formula is taken to be the MFE structure, as computed by RNAfold -d2. If the optional input {Delta} is missing, then {Delta} is defined to equal the length n of the input sequence Formula ; otherwise {Delta} is the minimum of the input value and n. For each 0 ≤ {delta} ≤ {Delta}, RNAbor computes the Boltzmann probability p{delta} = Z{delta} /Z, where the partition function is defined by

Formula
where R is the universal gas constant and T is temperature in degrees Kelvin. Here, the summation is made over all secondary structures Formula of Formula which are {delta}-neighbors of Formula . The full partition function Z = {sum} {delta} Z{delta} is computed by McCaskill's algorithm (8) if {Delta} ≥ n.

In addition to computing probability p{delta}, RNAbor computes the number N{delta} of {delta}-neighbors of Formula , the MFE{delta} over all {delta}-neighbors of Formula and the MFE{delta} secondary structure. Tables of the values N{delta} and p{delta}, as well as their graphs, are made available as downloadable files. The five-column text file output, consisting of {delta}, p{delta}, N{delta}, MFE{delta} and the MFE{delta} structure, is depicted in Figure 1.


Figure 1
View larger version (37K):
[in this window]
[in a new window]
[Download PowerPoint slide]
  		Figure 1. Text output of RNAbor on the 51 nt 3 ' UTR of a mRNA with NCBI accession number MUSGBPS. The five columns in the entire text output from RNAbor are given by the following, in order: (i) value of {delta}, (ii) Boltzmann probability p{delta}, (iii) number of {delta}-neighbors, (iv) MFE of {delta}-neighbors, denoted MFE{delta}, (v) MFE secondary structure among all {delta}-neighbors. In this case, the initial structure is the MFE structure, as determined by RNAfold -d2.

 

   EXAMPLES
TOP
 ABSTRACT
 INTRODUCTION
 MATERIALS AND METHODS
 RESULTS
 EXAMPLES
DISCUSSION
 REFERENCES
 
RNAbor can be used to generate alternative low energy structures, which differ markedly from the MFE structure, or from any initially given structure. Figure 1 shows the RNAbor output for a short 3 '-UTR sequence of an mRNA with NCBI accession number MUSGBPS. The input structure in this example is the MFE structure (as predicted by RNAfold -d2). The RNAbor output indicates two ranges of {delta} that show higher probabilities than the rest, 0–9 and 20–24. The MFE{delta} structures at distance {delta} between 0 and 9 from the MFE structure all have very similar folds and the probability of finding the RNA in a structure at {delta} between 0 and 9 is 0.63. The probability of finding a structure at {delta} 20–24 is also relatively high, 0.35, and the MFE{delta} structures in this range are similar to each other but completely different from the MFE structure. Thus the two highly probable {delta} ranges represent two possible alternative folds of the RNA.

Analyzing the same sequence with Sfold gives similar results. Sfold finds three types of structures (three clusters), with probabilities 0.65, 0.22 and 0.13, respectively. One cluster contains the MFE structure corresponding to the folds at {delta} values from 0 to 9, another cluster has a centroid structure resembling the structures at {delta} between 20 and 24, and the third cluster has a centroid structure similar to the MFE19 structure. RNAshapes on the other hand is less successful for this example since the alternative folds as predicted by RNAbor have the same shape [ ], even though the folds are very different.

Figure 2 displays the MFE structure and the MFE30 structure of the 101 nt SAM riboswitch with EMBL accession number AP004597.1/118941-119041, with sequence taken from Rfam (17). The MFE structure over all 30-neighbors, the MFE30 structure, is clearly much closer to the real structure than the global MFE structure. Figure 3 displays the Boltzmann probability density, showing a peak for the value {delta} = 30.


Figure 2
View larger version (11K):
[in this window]
[in a new window]
[Download PowerPoint slide]
  		Figure 2. Two alternative low energy secondary structures for the 101 nt SAM riboswitch with EMBL accession number AP004597.1 from position 118941 to position 119041. This riboswitch has nucleotide sequence UACUUAUCAA GAGAGGUGGA GGGACUGGCC CGCUGAAACC UCAGCAACAG AACGCAUCUG UCUGUGCUAA AUCCUGCAAG CAAUAGCUUG AAAGAUAAGU U. Panel (a) displays the MFE structure with free energy –33.30 kcal/mol, while (b) displays the 30-neighbor of the MFE with free energy of –32.10 kcal/mol. The only significant Boltzmann probabilities were for values around {delta} = 0 and {delta} = 30, where p0 = 0.056238 and p30 = 0.151751. Note that the MFE30 structure more closely resembles the expected structure for a riboswitch shown in (c), as determined from the Rfam (17) consensus structure.

 

Figure 3
View larger version (9K):
[in this window]
[in a new window]
[Download PowerPoint slide]
  		Figure 3. Boltzmann probability density plot for the 101 nt SAM riboswitch (EMBL accession number AP004597.1/118941-119041). The curve shows the probability, p{delta} = Z{delta} / Z, for all secondary structures of RNA sequence Figure 3 having base pair distance {delta} from the MFE structure Figure 3.

 

   DISCUSSION
TOP
 ABSTRACT
 INTRODUCTION
 MATERIALS AND METHODS
 RESULTS
 EXAMPLES
 DISCUSSION
REFERENCES
 
In this article, we have introduced the web server RNAbor, which computes the Boltzmann probability and MFE structure over all {delta}-neighbors for a given RNA sequence Formula and initial secondary structure Formula . The underlying algorithms, described in the forthcoming paper (Freyhult, E., Moulton, V. and Clote, P. Boltzmann probability of RNA structural neighbors and riboswitch detection, submitted for publication), use dynamic programming, involve the Turner energy model (15,16), and require considerable time O({Delta} · n3) and space O({Delta} · n2) resources. Figures 2 and 3 illustrate the use of RNAbor in better understanding structural aspects of a SAM riboswitch, and indicate that RNAbor should provide a useful complementary tool to programs such as Sfold and RNAshapes for analyzing the ensemble of possible secondary structures on a given RNA sequence.


   ACKNOWLEDGEMENTS
 
Research of P.C. was partially supported by National Science Foundation DBI-0543506, which additionally supported some travel of E.F. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation. All three authors would like to thank Elena Rivas, Eric Westhof and funding agencies for organizing the meeting RNA-2006 in Benasque, Spain, in July 2006, where some of this work was carried out. Finally, thanks to Jason Persampieri for some technical assistance. Funding to pay the Open Access publication charges for this article was provided by the National Science Foundation.

Conflict of interest statement. None declared.


   REFERENCES
TOP
 ABSTRACT
 INTRODUCTION
 MATERIALS AND METHODS
 RESULTS
 EXAMPLES
 DISCUSSION
 REFERENCES
 

  1. Doudna JA, Cech TR. The chemical repertoire of natural ribozymes. Nature (2002) 418:222–228.[CrossRef][Medline]

  2. Winkler WC, Cohen-Chalamish S, Breaker RR. An mRNA structure that controls gene expression by binding FMN. Proc. Natl Acad. Sci. USA (2002) 99:15908–15913.[Abstract/Free Full Text]

  3. Penchovsky R, Breaker RR. Computational design and experimental validation of oligonucleotide-sensing allosteric ribozymes. Nat. Biotechnol (2005) 23:1424–1431.[CrossRef][Web of Science][Medline]

  4. Mathews DH, Turner DH. Prediction of RNA secondary structure by free energy minimization. Curr. Opin. Struct. Biol (2006) 16:270–278.[CrossRef][Web of Science][Medline]

  5. Eddy SR. Non-coding RNA genes and the modern RNA world. Nat. Rev. Genet (2001) 2:919–929.[CrossRef][Web of Science][Medline]

  6. Ding Y, Lawrence CE. A statistical sampling algorithm for RNA secondary structure prediction. Nucleic Acids Res (2003) 31:7280–7301.[Abstract/Free Full Text]

  7. Ding Y, Chan CY, Lawrence CE. RNA secondary structure prediction by centroids in a Boltzmann weighted ensemble. RNA (2005) 11:1157–1166.[Abstract/Free Full Text]

  8. McCaskill JS. The equilibrium partition function and base pair binding probabilities for RNA secondary structures. Biopolymers (1990) 29:1105–1119.[CrossRef][Web of Science][Medline]

  9. Wuchty S, Fontana W, Hofacker IL, Schuster P. Complete suboptimal folding of RNA and the stability of secondary structures. Biopolymers (1999) 49:145–164.[CrossRef][Web of Science][Medline]

  10. Giegerich R, Voss B, Rehmsmeier M. Abstract shapes of RNA. Nucleic Acids Res (2004) 32:4843–4851.[Abstract/Free Full Text]

  11. Steffen P, Voss B, Rehmsmeier M, Reeder J, Giegerich R. RNAshapes: an integrated RNA analysis package based on abstract shapes. Bioinformatics (2006) 22:500–503.[Abstract/Free Full Text]

  12. Voss B, Giegerich R, Rehmsmeier M. Complete probabilistic analysis of RNA shapes. BMC Biol (2006) 4:5.[CrossRef][Medline]

  13. James W. Nucleic acid and polypeptide aptamers: a powerful approach to ligand discovery. Curr. Opin. Pharmacol (2001) 1:540–548.[CrossRef][Medline]

  14. Moulton V, Zuker M, Steel M, Pointon R, Penny D. Metrics on RNA secondary structures. J. Comput. Biol (2000) 7:277–292.[CrossRef][Web of Science][Medline]

  15. Matthews DH, Sabina J, Zuker M, Turner DH. Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure. J. Mol. Biol (1999) 288:911–940.[CrossRef][Web of Science][Medline]

  16. Xia T, SantaLucia J Jr, Burkard ME, Kierzek R, Schroeder SJ, Jiao X, Cox C, Turner DH. Thermodynamic parameters for an expanded nearest-neighbor model for formation of RNA duplexes with Watson-Crick base pairs. Biochemistry (1998) 37:14719–14735.[CrossRef][Medline]

  17. Griffiths-Jones S, Bateman A, Marshall M, Khanna A, Eddy SR. Rfam: an RNA family database. Nucleic Acids Res (2003) 31:439–441.[Abstract/Free Full Text]


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?


This article has been cited by other articles:


Home page
 Nucleic Acids ResHome page
J. Waldispuhl, S. Devadas, B. Berger, and P. Clote
RNAmutants: a web server to explore the mutational landscape of RNA secondary structures
Nucleic Acids Res., July 1, 2009; 37(suppl_2): W281 - W286.
[Abstract] [Full Text] [PDF]

This Article
Right arrow Abstract Freely available
Right arrow Print PDF (1707K) Freely available
Right arrow Screen PDF (273K) Freely available
Right arrowOA All Versions of this Article:
35/suppl_2/W305    most recent
gkm255v1
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in PubMed
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrow Commercial Re-use Guidelines
for Open Access NAR Content
Google Scholar
Right arrow Articles by Freyhult, E.
Right arrow Articles by Clote, P.
Right arrow Search for Related Content
PubMed
Right arrow PubMed Citation
Right arrow Articles by Freyhult, E.
Right arrow Articles by Clote, P.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?