Skip Navigation


Bioinformatics Advance Access originally published online on January 29, 2006
Bioinformatics 2006 22(10):1177-1182; doi:10.1093/bioinformatics/btl024
This Article
Right arrow Abstract Freely available
Right arrow FREE Full Text (Print PDF) Freely available
Right arrow All Versions of this Article:
22/10/1177    most recent
btl024v1
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 ISI Web of Science
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 Search for citing articles in:
ISI Web of Science (8)
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Mückstein, U.
Right arrow Articles by Hofacker, I. L.
Right arrow Search for Related Content
PubMed
Right arrow PubMed Citation
Right arrow Articles by Mückstein, U.
Right arrow Articles by Hofacker, I. L.
Social Bookmarking
 Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author 2006. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

Thermodynamics of RNA–RNA binding

Ulrike Mückstein 1, Hakim Tafer 1, Jörg Hackermüller 2, Stephan H. Bernhart 1, Peter F. Stadler 1,3,4 and Ivo L. Hofacker 1,*

1 Institute for Theoretical Chemistry, University of Vienna Währingerstrasse 17, A-1090 Vienna, Austria
2 Fraunhofer Institut für Zelltherapie und Immunologie, IZI Deutscher Platz 5e, D-04103 Leipzig, Germany
3 Bioinformatics Group, Department of Computer Science, and Interdisciplinary Center for Bioinformatics, University of Leipzig Härtelstrasse 16-18, D-04107 Leipzig, Germany
4 The Santa Fe Institute 1399 Hyde Park Rd., Santa Fe, New Mexico

*To whom correspondence should be addressed.


    ABSTRACT
 TOP
 ABSTRACT
 1 INTRODUCTION
 2 ENERGY-DIRECTED RNA FOLDING
 3 PROBABILITY OF AN...
 4 INTERACTION PROBABILITIES
 5 RESULTS
 6 CONCLUDING REMARKS
 REFERENCES
 

Background: Reliable prediction of RNA–RNA binding energies is crucial, e.g. for the understanding on RNAi, microRNA–mRNA binding and antisense interactions. The thermodynamics of such RNA–RNA interactions can be understood as the sum of two energy contributions: (1) the energy necessary to ‘open’ the binding site and (2) the energy gained from hybridization.

Methods: We present an extension of the standard partition function approach to RNA secondary structures that computes the probabilities Pu[i, j] that a sequence interval [i, j] is unpaired.

Results: Comparison with experimental data shows that Pu[i, j] can be applied as a significant determinant of local target site accessibility for RNA interference (RNAi). Furthermore, these quantities can be used to rigorously determine binding free energies of short oligomers to large mRNA targets. The resource consumption is comparable with a single partition function computation for the large target molecule. We can show that RNAi efficiency correlates well with the binding energies of siRNAs to their respective mRNA target.

Availability: RNAup will be distributed as part of the Vienna RNA Package, www.tbi.univie.ac.at/~ivo/RNA/

Contact: ivo{at}tbi.univie.ac.at


    1 INTRODUCTION
 TOP
 ABSTRACT
 1 INTRODUCTION
 2 ENERGY-DIRECTED RNA FOLDING
 3 PROBABILITY OF AN...
 4 INTERACTION PROBABILITIES
 5 RESULTS
 6 CONCLUDING REMARKS
 REFERENCES
 
Secondary structure prediction for a single RNA molecule is a classical problem of computational biology, which has received increasing attention in recent years owing to mounting evidence that emphasizes the importance of RNA structure in a wide variety of biological processes (Kretschmer-Kazemi Far and Sczakiel, 2003; Overhoff et al., 2005; Schubert et al., 2005; Parker et al., 2005). Despite its limitations, free energy minimization (Turner et al., 1988; Zuker and Stiegler, 1981; Zuker, 2000) is at present the most accurate and most generally applicable approach of RNA structure prediction, at least in the absence of a large set of homologous sequences. It is based upon a large number of measurements performed on small RNAs and the assumption that stacking base pairs and loop entropies contribute additively to the free energy of an RNA secondary structure (Mathews et al., 1999a; Mathews, 2004). In this framework, a secondary structure is interpreted as the collection of all the three-dimensional structures that share a common pattern of base pairs, hence we speak of a free energy of an individual secondary structure.

Under the assumption that RNA secondary structures are pseudo-knot free, i.e. that base pairs do not cross1, there are efficient exact dynamic programming algorithms that solve not only the folding problem (Zuker, 1989) but also provide access to the full thermodynamics of the model via its partition function (McCaskill, 1990). Two widely used software packages implementing these algorithms are available, mfold (Zuker, 2000; Zuker and Stiegler, 1981) and the Vienna RNA Package (Hofacker et al., 1994; Hofacker, 2003).

More recently, the secondary structure approach has been applied to the problem of interacting RNA molecules. In the simplest approaches secondary structures within both monomers are omitted for the sake of computational speed, so that only intermolecular base pairs are taken into account. This is implemented in the program RNAhybrid (Rehmsmeier et al., 2004) as well as RNAduplex from the Vienna RNA package, see also (Zuker, 2003; Dimitrov and Zuker, 2004). The program bindigo uses a variation of the Smith–Waterman sequence alignment algorithm for the same purpose (Hodas and Aalberts, 2004). OligoWalk (Mathews et al., 1999b) considers the stability of a oligonucleotide-target helix as well as the competition with predicted secondary structure of both target and oligonucleotide using the optimal structure and, optionally, suboptimal structures.

A biophysically more plausible model is the ‘co-folding’ of two RNAs. Algorithmically, this is very similar to folding a single RNA molecule. The idea is to concatenate the two sequences and to use different energy parameters for the loop that contains the cut-point between the two sequences. A corresponding RNAcofold program for calculation of the minimum free energy structure is described in Hofacker et al. (1994), the pairfold program (Andronescu et al., 2005) also computes suboptimal structures in the spirit of RNAsubopt (Wuchty et al., 1999). The first microRNA target prediction programs approximated the cofolding of two RNAs by applying the standard folding algorithm to an artificial sequence consisting of the putative target site, a ‘linker’ sequence and the microRNA, see e.g. Stark et al. (2003).

The restriction of the folding algorithm to pseudo-knot-free structures, however, excludes a large set of structures that should not be excluded when studying the hybridization of a short oligonucleotide to a large mRNA. In particular, binding of the oligo is in practice not restricted to the exterior loop of the target RNA, as is implicitly assumed in the RNAcofold approach. On the other hand, there is no biophysically plausible reason to exclude elaborate secondary structures in the target molecule (as in the case of RNAduplex and RNAhybrid).

Here we extend previous RNA/RNA cofold algorithms by taking into account that the oligo can bind also to unpaired sequences in hairpin, interior, or multi-branch loops. These cases could in principle be handled using a generic approach to pseudo-knotted RNA structures (Dirks and Pierce, 2003, 2004) at the expense of much more costly computations. Instead we conceptually decompose RNA/RNA binding into two stages: (1) We calculate the partition function for secondary structures of the target RNAs subject to the constraint that a certain sequence interval (the binding site) remains unpaired. (2) We then compute the interaction energies given that the binding site is unpaired in the target. The total interaction probability at a possible binding site is then obtained as the sum over all possible types of binding. The advantage is that the memory and CPU requirements are drastically reduced: For a target RNA of length n and an oligo of length w < n we need only Formula memory and Formula time [compared with Formula memory and Formula time for folding the target alone].

We apply this approach to published data from RNAi experiments (Schubert et al., 2005): we demonstrate that siRNA/mRNA binding can be quantitatively predicted by our procedure. The predicted binding energies correlate well with expression data, showing that the effect of RNAi depends quantitatively on siRNA/mRNA binding. In addition to assessing the interactions at known binding sites, our approach also provides an effective way of identifying alternative binding sites, since the computational effort for scanning target mRNA is small compared with the initial partition function calculation. RNAup is therefore ideally suited to study RNA–RNA interactions in detail, in particular when the interaction partners are known or when a candidate set has already been obtained by faster, less accurate methods.


    2 ENERGY-DIRECTED RNA FOLDING
 TOP
 ABSTRACT
 1 INTRODUCTION
 2 ENERGY-DIRECTED RNA FOLDING
 3 PROBABILITY OF AN...
 4 INTERACTION PROBABILITIES
 5 RESULTS
 6 CONCLUDING REMARKS
 REFERENCES
 
All dynamic programming algorithms for RNA folding can be viewed as more sophisticated variants of the maximum circular matching problem (Nussinov et al., 1978). The basic idea is that each base pair in a secondary structure divides the structure into an interior and an exterior part that can be treated separately as a consequence of the additivity of the energy model. The problem of finding, say, the optimal structure of a subsequence [i, j] can thus be decomposed into the subproblems on the subsequence [i + 1, j] (provided i remains unpaired) and on pairs of intervals [i + 1, k – 1] and [k + 1, j] (provided i forms a base pair with some position k isin [i, j]). In the more realistic ‘loop-based’ energy models the same approach is used. In addition, however, one now has to distinguish between the possible types of loops that are enclosed by the pair (i, k) because hairpin loops interior loops and multiloops all come with different energetic contributions.

Algorithms that are designed to enumerate all structures (with a below-threshold energy) (Wuchty et al., 1999), that compute averages over all structures (McCaskill, 1990) or that sample from a [weighted Ding and Lawrence, 2003) or unweighted (Tacker et al., 1996)] ensemble of secondary structures, need to make sure that the decomposition of the structures into substructures is unique, so that each secondary structure is counted once and only once in the dynamic programming algorithm.

The basis of our algorithm is a modified version of the recursions for the equilibrium partition function introduced by McCaskill (1990) as implemented in the Vienna RNA package (Hofacker et al., 1994).


    3 PROBABILITY OF AN UNPAIRED REGION
 TOP
 ABSTRACT
 1 INTRODUCTION
 2 ENERGY-DIRECTED RNA FOLDING
 3 PROBABILITY OF AN...
 4 INTERACTION PROBABILITIES
 5 RESULTS
 6 CONCLUDING REMARKS
 REFERENCES
 
In the following let F(S) denote the free energy of a secondary structure S, and write ß for the inverse of the temperature times Boltzmann's constant. The equilibrium partition function is defined as Z = {sum}S exp(–ßF(S)). The partition function is the gateway to the thermodynamics of RNA folding. Quantities such as ensemble free energy, specific heat and melting temperature can be readily computed from Z and its temperature dependence.

Since the frequency of a structure S in equilibrium is given by P(S) = exp(–ßF(S))/Z, partition functions also provide the starting point for computing the frequency of a given structural motif. In particular we are interested in the probability Pu[i, j] that the sequence interval [i, j] is unpaired. Denoting the set of secondary structures in which [i, j] remains unpaired by Formula we have

Formula 1(1)
Clearly, the set Formula 1 will grow exponentially in general. The program Sfold (Ding and Lawrence, 2003; Ding et al., 2004) adds a stochastic backtracking procedure to McCaskill's partition function calculation (McCaskill, 1990) to generate a properly weighted sample of structures. One then simply counts the fraction of structures with the desired structural feature, e.g. single stranded regions. This approach to assess Pu[i, j] becomes inaccurate, however, when Pu[i, j] becomes smaller than the inverse of the sample size. Nevertheless, even very small probabilities Pu[i, j] can be of importance in the context of interacting RNAs, as we shall see below.

We therefore present here an exact algorithm. In the special case of an interval of length 1, i.e. a single unpaired base, Pu[i, i] can be computed by dynamic programming. Indeed, Pu[i, i] = 1 –{sum}j!=iPij, where Pij is the base pairing probability of pair (i, j), which is obtained directly from McCaskill's partition function algorithm (McCaskill, 1990). It is natural, therefore, to look for a generalization of the dynamic programming approach to longer unpaired stretches2.

We first observe that the unpaired interval [i, j] is either part of the ‘exterior loop’, (i.e. it is not enclosed by a basepair), or it is enclosed by a base pair (p, q) such that (p, q) is the closing pair of the loop that contains the unpaired interval [i, j]. We can therefore express Pu[i, j] in terms of restricted partition functions for these two cases:


Formula 2

(2)

The first term accounts for the ratio between the partition functions of all sub-structures on the 5' and 3' side of the interval [i, j] and the total partition function. In the second term, Zpq[i, j] is the partition function over all structures on the subsequence [p, q] subject to the restriction that [i, j] is unpaired and (p, q) forms a base pair, while Zb[p, q] counts all structures on [p, q] that form the pair (p, q). Multiplying the ratio of these two partition functions by the probability Ppq that (p, q) is indeed paired yields the desired fraction of structures in which [i, j] is left unpaired.

The tricky part of the algorithm is the computation of the restricted partition functions Zpq[i, j]. The recursion is built upon enumerating the possible types of loops that have (p, q) as their closing pair and contain [i, j], see Fig. 1. From this decomposition one derives:


Formula 3

(3)
where H(p, q) and I(p, q; k, l) are functions that compute the loop energies of hairpin and interior loops given their enclosing base pairs; c is an energy parameter for multiloops describing the penalty for increasing the loop size by one. The computation of the multiloop contributions (c–e) requires two additional types of restricted partitions functions: Zm[p, q] is the partition function of all conformations on the interval [p, q] that are part of a multiloop and contain at least one component, i.e. that contain at least one substructure that is enclosed by a base pair. These quantities are computed and tabulated already in the course of McCaskill's algorithm. There, the computation of Zm requires an auxiliary array Zm1 which counts structures in multiloops that have exactly one component, the closing pair of which starts at the first position of the interval. For the one-sided multiloop cases (c) and (e) in Fig. 1 we additionally need the partition functions of multiloop configurations that have at least two components. These are readily obtained using

Formula 4(4)
It is not hard to verify that this recursion corresponds to a unique decomposition of the ‘M2’ configurations into a 3' part that contains exactly one component and a 5' part with at least one component.


Figure 1
View larger version (5K):
[in this window]
[in a new window]
 
Fig. 1 A base pair p, q can close various loop types. According to the loop type different contributions have to be considered. (a) A hairpin loop is shown. (b) In case of an interior loop, two independent contributions to Zpq[i, j] are possible: The unstructured region [i, j] can be located on either side of the stacked pairs (p, q) and (k, l). (c–e) If region [i, j] is contained within a multiloop we have to account for three different conformations. A more detailed description is given in the text.

 
It is clear from the above recursions that, in comparison to McCaskill's partition function algorithm, we need to store only one additional matrix, Zm2. The CPU requirements increase to Formula 4 (assuming the usual restriction of the length of interior loops). In practice, however, the probabilities for very long unpaired intervals are negligible, so that Pu[i, j] is of interest only for limited interval length |ji + 1| ≤ w. Taking this constraint into account shows that the CPU requirements are actually only Formula 4.


    4 INTERACTION PROBABILITIES
 TOP
 ABSTRACT
 1 INTRODUCTION
 2 ENERGY-DIRECTED RNA FOLDING
 3 PROBABILITY OF AN...
 4 INTERACTION PROBABILITIES
 5 RESULTS
 6 CONCLUDING REMARKS
 REFERENCES
 
The values of Pu[i, j] can be of interest in their own right: Hackermüller, Meisner and collaborators (Hackermüeller et al., 2005; Meisner et al., 2004) showed that the binding of the HuR protein to its mRNA target is proportional to the probability that the HuR binding site has an unpaired conformation. While not much is known about the energetics of RNA–protein interactions, the case of RNA–RNA interactions can be modeled in more detail: The energetics of RNA–RNA interactions is viewed as a stepwise process, {Delta}G = {Delta}Gu + {Delta}Gh, in which the free energy of binding consists of the contribution {Delta}Gu that is necessary to expose the binding site in the appropriate conformation, and contribution {Delta}Gh that describes the energy gain because of hybridization at the binding site. This additivity assumes that the energy of the original loop is unchanged by the binding of the oligo. For an unpaired binding motif in the interval [i, j], we have of course {Delta}Gu = (–1/ß)(ln Zu[i, j]– ln Z) = (–1/ß) ln Pu[i, j]. Since the energy gain from the hybridization can be substantial, it becomes necessary to deal also with very small values of Pu[i, j]. The sampling approach thus becomes infeasible.

The computation of the hybridization part is performed similar to RNAduplex or RNAhybrid: We assume that the binding region may contain mismatches and bulge loops. Thus the partition function over all interactions between a region [i*, j*] in the small RNA and a segment [i, j] in the target RNA is obtained recursively by summing over all possible interior loops closed by base pairs (k, k*) and (j, j*), see Figure 2.

Formula 5(5)
Since we are mostly interested in the binding of small RNAs, e.g. miRNAs and siRNAs to a target mRNA, we will neglect internal structures in the short RNA and include unfolding of the mRNA target site. Thus only ZI and Pu[i, j] are needed to compute Z*[i, j], the partition function over all structures where the short RNA binds to region [i, j], and for the computation of the corresponding binding probability, P*[i, j].

Formula 6(6)
From P*[i, j] we can readily compute the probability Formula 6 that a position k lies somewhere within the binding site. Note that these are conditional probabilities given that the two molecules bind at all. Furthermore Z*[i, j] can be used to calculate {Delta}G[ij] = (–1/ß) ln Z*[i, j] the free energy of binding, where the binding site is in region [i, j]. For visual inspection {Delta}G[ij] can be reduced to the optimal free energy of binding at a given position i, {Delta}Gi = mink≤i≤l {{Delta}G[kl]}. The memory requirement for these steps is Formula 6, the required CPU time scales as Formula 6, which at least for long target RNAs is dominated by the first step, i.e. the computation of the Pu[i, j].


Figure 2
View larger version (9K):
[in this window]
[in a new window]
 
Fig. 2 Calculation of the probability of an interaction between a short RNA and its target.

 

    5 RESULTS
 TOP
 ABSTRACT
 1 INTRODUCTION
 2 ENERGY-DIRECTED RNA FOLDING
 3 PROBABILITY OF AN...
 4 INTERACTION PROBABILITIES
 5 RESULTS
 6 CONCLUDING REMARKS
 REFERENCES
 
In order to demonstrate that our algorithm produces biologically reasonable results, we compared predicted free energies of binding with data from RNA interference experiments. Small interfering RNAs (siRNAs) are short (21–23 nt) RNA duplices with symmetric 2–3 nt overhangs (Dykxhoorn et al., 2003; Meister and Tuschl, 2004; Mittal, 2004). They are used to silence gene expression in a sequence-specific manner in a process known as RNA interference (RNAi). Recently, there has been mounting evidence that the biological activity of siRNAs is influenced by local structural characteristics of the target mRNA (Mittal, 2004; Kretschmer-Kazemi Far and Sczakiel, 2003; Bohula et al., 2003; Yoshinari et al., 2004; Overhoff et al., 2005; Schubert et al., 2005; Robins et al., 2005): a target sequence must be accessible for hybridization in order to achieve efficient translational repression. An obstacle for effective application of siRNAs is the fact that the extent of gene inactivation by different siRNAs varies considerably. Several groups have proposed basically empirical rules for designing functional siRNAs, see e.g. Elbashir et al. (2002) and Reynolds et al. (2004), but the efficiency of siRNAs generated using these rules is highly variable. Recent contributions (Parker et al., 2005; Schubert et al., 2005) suggest two significant parameters: The stability difference between 5' and 3' end of the siRNA, that determines which strand is included into the RISC complex (Khvorova et al., 2003; Schwarz et al., 2003) and the local secondary structure of the target site (Schubert et al., 2005; Overhoff et al., 2005; Mittal, 2004; Kretschmer-Kazemi Far and Sczakiel, 2003; Bohula et al., 2003; Yoshinari et al., 2004).

Schubert et al. (2005) systematically analyzed the contribution of mRNA structure to siRNA activity. They designed a series of constructs, all containing the same target site for the same siRNA. These binding sites, however, were sequestered in local secondary structure elements of different stability and extension. They observed a significant obstruction of gene silencing for the same siRNA caused by structural features of the substrate RNA. A clear correlation was found between the number of exposed nucleotides and the efficiency of gene silencing: When all nucleotides were incorporated in a stable hairpin, silencing was reduced drastically, while exposure of 16 n resulted in efficient inhibition of expression virtually indistinguishable from the wild type.

We applied our methods to study the target sites provided by Schubert et al. (2005). Our predictions, shown in Figure 3, are in perfect agreement with the experimental results. The target site of the ‘VR1straight’ construct has a high probability of being unstructured, consequently {Delta}Gi, the optimal free energy of binding, is highly favorable and the siRNA will bind almost exclusively to the intended target site. The stepwise reduction of the target accessibility is directly correlated to a weaker optimal free energy of binding and decreasing silencing efficiency. In case of construct VR HP5_6 the optimal free energy of binding at an alternative binding site at positions 1066 to 1078 nearly equals that at the proposed target site. Since siRNAs can also function as miRNAs (Doench et al., 2003; Zeng et al., 2003), the siRNA might act in a miRNA like fashion binding to this alternative target site and contribute to the remaining translational repression of this construct. The incomplete complementarity of the siRNA to the alternative target site should be no obstacle to functionality, since it was shown that miRNAs can be active even if the longest continuous helix with the target site is as short as 4–5 bp (Brennecke et al., 2005).


Figure 3
View larger version (30K):
[in this window]
[in a new window]
 
Fig. 3 Probability of being unpaired Pu[i, i] (dashed line), probability of binding to siRNA at position i, Formula 6, (thick black line) and {Delta}Gi, the optimal free energy of binding in a region including position i (thick grey line) near the known target site of VsiRNA1. The scale for the probabilities is indicated on the left side, the scale for the minimal free energy of binding on the right side. At the bottom the protein expression levels in experimental data (Schubert et al., 2005) are indicated. The isolated 21mer target sequence, displaying the same activity as the wild-type mRNA and three mutants are shown. A decreasing optimal free energy of binding is correlated with increasing expression. In the case of the HP5_6 mutant an alternative binding site becomes occupied as the optimal free energy of binding due to this alternative interaction nearly equals {Delta}Gi at the proposed target site.

 
Our new accessibility prediction tool can thus be used to analyze potential binding sites as well as explain differences in si/miRNA efficiency caused by secondary structure effects.


    6 CONCLUDING REMARKS
 TOP
 ABSTRACT
 1 INTRODUCTION
 2 ENERGY-DIRECTED RNA FOLDING
 3 PROBABILITY OF AN...
 4 INTERACTION PROBABILITIES
 5 RESULTS
 6 CONCLUDING REMARKS
 REFERENCES
 
We have demonstrated here that variants of McCaskill's partition function algorithm can be implemented efficiently to compute the probability that a given sequence interval [i, j] is unpaired. The computation is rigorous and can thus be used even for small probabilities, i.e. in cases where large free energy changes are necessary to expose a binding site. Since these free energy changes are compensated sometimes by substantial hybridization energies, as in the case siRNA/mRNA binding, even very small probabilities have to be included. The approach presented here therefore overcomes inherent limitations in sampling approaches at a small computational cost. Conceptually, it is not hard to extend this approach to other structural features, see also (Flamm et al., 2004). In practice, however, general purpose implementations are at least tedious. Such practical limitations can be circumvented, however, in the framework of Algebraic Dynamic Programming, as exemplified in RNAshapes (Giegerich et al., 2004) which allows computations with RNA structures subject to constraints on a coarse grained level.

RNAup is by itself not fast enough for genome-wide predictions of microRNA or siRNA targets. It can, however, be combined easily with faster methods for assessing RNA–RNA interactions, such as RNAhybrid and RNAduplex, or with other microRNA target prediction programs [see Bentwich (2005) and Brennecke et al. (2005) for reviews] that are fast enough for genome-wide screens. The resulting candidate sets can then be processes further by RNAup.

In our exposition above, all probabilities are conditional probabilities given that the molecules interact at all. Comparison with the partition function of the isolated systems and standard statistical thermodynamics, however, can be used to explicitly compute the concentration dependence of RNA–RNA binding, see e.g. Dimitrov and Zuker, (2004). A more general limitation is our lack of knowledge concerning the energetics of RNA–RNA interactions within loops: the binding of the oligo to a loop will of course alter the energy contribution of the loop itself. In the model above we have implicitly assumed that this energy change is a constant. Additional measurement along the lines of the investigation of kissing-interactions (Weixlbaumer et al., 2004) are required to improve the energy parameters for interacting RNAs.

In context of RNA silencing it should be noted that efficiency is not only a function of thermodynamics of RNA–RNA interaction but will also depend on protein factors. As long as the binding energies of the protein component(s) are independent of the RNA sequences our approach is still useful since it correctly reproduces at least the relative order of RNA–RNA binding energies. A further concern is whether the underlying assumption of thermodynamically controlled binding is correct; it is possible that in particular when RNA binding is associated with large structural changes, kinetic effects of structure formation might be important. Nevertheless, one would expect that even a kinetically controlled structure will energetically be close to the ground state, in which case RNAup at least provides a meaningful approximation to the energetics of the interaction.


    Acknowledgments
 
This work was supported in part by the Austrian Fonds zur Förderung der Wissenschaftlichen Forschung, Project No. P15893 [GenBank] , by the Austrian Gen-AU bioinformatics integration network and by the German DFG Bioinformatics Initiative BIZ-6/1-2.

Conflict of Interest: none declared.


    FOOTNOTES
 
Associate Editor: Thomas Lengauer

1Two base pairs (i, j) and (k, l) are crossing if i < k < j < l. Back

2Note that we cannot simply use Formula 6 Pu[k, k] since these probabilities are not even approximately independent. Back

Received on November 18, 2005; revised on December 22, 2005; accepted on January 23, 2006

    REFERENCES
 TOP
 ABSTRACT
 1 INTRODUCTION
 2 ENERGY-DIRECTED RNA FOLDING
 3 PROBABILITY OF AN...
 4 INTERACTION PROBABILITIES
 5 RESULTS
 6 CONCLUDING REMARKS
 REFERENCES
 

    Andronescu, M., et al. (2005) Secondary structure prediction of interacting RNA molecules. J. Mol. Biol, . 345, 987–1001[CrossRef][ISI][Medline].

    Bentwich, I. (2005) Prediction and validation of microRNAs and their targets. FEBS Lett, . 579, 5904–5910[CrossRef][ISI][Medline].

    Bohula, E.A., et al. (2003) The efficacy of small interfering RNAs targeted to the type 1 insulin-like growth factor receptor (IGF1R) is influenced by secondary structure in the IGF1R transcript. J. Biol. Chem, . 278, 15991–15997[Abstract/Free Full Text].

    Brennecke, J., et al. (2005) Principles of microRNA-target recognition. PLoS Biol, . 3, e85[CrossRef][Medline].

    Dimitrov, R.A. and Zuker, M. (2004) Prediction of hybridization and melting for double-stranded nucleic acids. Biophys. J, . 87, 215–226[Abstract/Free Full Text].

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

    Ding, Y., et al. (2004) Sfold web server for statistical folding and rational design of nucleic acids. Nucleic Acids Res, . 32, W135–W141[Abstract/Free Full Text].

    Dirks, R. and Pierce, N. (2003) A partition function algorithm for nucleic acid secondary structure including pseudoknots. J. Comput. Chem, . 24, 1664–1677[CrossRef][ISI][Medline].

    Dirks, R. and Pierce, N. (2004) An algorithm for computing nucleic acid base-pairing probabilities including pseudoknots. J. Comput. Chem, . 25, 1295–1304[CrossRef][ISI][Medline].

    Doench, J., et al. (2003) siRNAs can function as miRNAs. Genes Dev, . 17, 438–442[Abstract/Free Full Text].

    Dykxhoorn, D., et al. (2003) Killing the messenger: short RNAs that silence gene expression. Nat. Rev. Mol. Cell Biol, . 4, 457–467[CrossRef][ISI][Medline].

    Elbashir, S., et al. (2002) Analysis of gene function in somatic mammalian cells using small interfering RNAs. Methods, 26, 199–213[CrossRef][ISI][Medline].

    Flamm, C., et al. (2004) Computational chemistry with RNA secondary structures. Kemija u industriji, 53, 315–322 (Proceedings CECM-2 Varazdin 2003).

    Giegerich, R., et al. (2004) Abstract shapes of RNA. Nucleic Acids Res, . 32, 4843–4851[Abstract/Free Full Text].

    Hackermüller, J., et al. (2005) The effect of RNA secondary structures on RNA-ligand binding and the modifier RNA mechanism: A quantitative model. Gene, 345, 3–12[CrossRef][ISI][Medline].

    Hodas, N. and Aalberts, D. (2004) Efficient computation of optimal oligo-RNA binding. Nucleic Acids Res, . 32, 6636–6642[Abstract/Free Full Text].

    Hofacker, I.L., et al. (1994) Fast folding and comparison of RNA secondary structures. Monatsh. Chem, . 125, 167–188[CrossRef].

    Hofacker, I. (2003) Vienna RNA secondary structure server. Nucleic Acids Res, . 31, 3429–3431[Abstract/Free Full Text].

    Khvorova, A., et al. (2003) Functional siRNAs and miRNAs exhibit strand bias. Cell, 115, 209–16[CrossRef][ISI][Medline].

    Kretschmer-Kazemi Far, R. and Sczakiel, G. (2003) The activity of siRNA in mammalian cells is related to structural target accessibility: acomparison with antisense oligonucleotides. Nucleic Acids Res, . 31, 4417–4424[Abstract/Free Full Text].

    Mathews, D.H. (2004) Using an RNA secondary structure partition function to determine confidence in base pairspredicted by free energy minimization. RNA, 10, 1178–1190[Abstract/Free Full Text].

    Mathews, D.H., et al. (1999a) Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure. J. Mol. Biol, . 288, 911–940[CrossRef][ISI][Medline].

    Mathews, D., et al. (1999b) Predicting oligonucleotide affinity to nucleic acid targets. RNA, 5, 1458–1469[Abstract].

    McCaskill, J.S. (1990) The equilibrium partition function and base pair binding probabilities for RNA secondary structures. Biopolymers, 29, 1105–1119[CrossRef][ISI][Medline].

    Meisner, N.-C., et al. (2004) mRNA openers and closers: A methodology to modulate AU-rich element controlled mRNA stability by a molecular switch in mRNA conformation. Chembiochem, . 5, 1432–1447[CrossRef][ISI][Medline].

    Meister, G. and Tuschl, T. (2004) Mechanisms of gene silencing by double-stranded RNA. Nature, 431, 343–349[CrossRef][Medline].

    Mittal, V. (2004) Improving the efficiency of RNA interference in mammals. Nat. Rev. Genet, . 5, 355–365[ISI][Medline].

    Nussinov, R., et al. (1978) Algorithms for Loop Matching. SIAM J. Appl. Math, . 35, 68–82[CrossRef].

    Overhoff, M., et al. (2005) Local RNA target structure influences siRNA efficacy: A systematic global analysis. J. Mol. Biol, . 348, 871–881[CrossRef][ISI][Medline].

    Parker, J.S., et al. (2005) Structural insights into mRNA recognition from a PIWI domain-siRNA guide complex. Nature, 434, 663–666[CrossRef][Medline].

    Rehmsmeier, M., et al. (2004) Fast and effective prediction of microRNA/target duplexes. RNA, 10, 1507–1517[Abstract/Free Full Text].

    Reynolds, A., et al. (2004) Rational siRNA design for RNA interference. Nat. Biotechnol, . 22, 326–330[CrossRef][ISI][Medline].

    Robins, H., et al. (2005) Incorporating structure to predict microRNA targets. Proc. Natl Acad. Sci. USA, 102, 4006–4009[Abstract/Free Full Text].

    Schubert, S., et al. (2005) Local RNA Target structure influences siRNA efficacy: Systematic analysis of intentionally designed binding regions. J. Mol. Biol, . 348, 883–893[CrossRef][ISI][Medline].

    Schwarz, D., et al. (2003) Asymmetry in the assembly of the RNAi enzyme complex. Cell, 115, 99–208.

    Stark, A., et al. (2003) Identification of Drosophila microRNA targets. PLoS Biol, . 1, e60.

    Tacker, M., et al. (1996) Algorithm independent properties of RNA structure prediction. Eur. Biophy. J, . 25, 115–130[CrossRef].

    Turner, D., et al. (1988) RNA structure prediction. Annu. Rev. Biophys. Biophys. Chem, . 17, 167–192[CrossRef][ISI][Medline].

    Weixlbaumer, A., et al. (2004) Determination of thermodynamic parameters for HIV DIS type loop–loop kissing complexes. Nucleic Acids Res, . 32, 5126–5133[Abstract/Free Full Text].

    Wuchty, S., et al. (1999) Complete suboptimal folding of RNA and the stability of secondary structures. Biopolymers, 49, 145–165[CrossRef][ISI][Medline].

    Yoshinari, K., et al. (2004) Effects on RNAi of the tight structure, sequence and position of the targeted region. Nucleic Acids Res, . 32, 691–699[Abstract/Free Full Text].

    Zeng, Y., et al. (2003) MicroRNAs and small interfering RNAs can inhibit mRNA expression by similar mechanisms. Proc. Natl Acad. Sci. USA, 100, 9779–9784[Abstract/Free Full Text].

    Zuker, M. (1989) On finding all suboptimal foldings of an RNA molecule. Science, 7, 48–52.

    Zuker, M. (2000) Calculating nucleic acid secondary structure. Curr. Opin. Struct. Biol, . 10, 303–310[CrossRef][ISI][Medline].

    Zuker, M. (2003) Mfold web server for nucleic acid folding and hybridization prediction. Nucleic Acids Res, . 31, 3406–3415[Abstract/Free Full Text].

    Zuker, M. and Stiegler, P. (1981) Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information. Nucleic Acids Res, . 9, 133–148[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
A. R. Gruber, R. Lorenz, S. H. Bernhart, R. Neubock, and I. L. Hofacker
The Vienna RNA Websuite
Nucleic Acids Res., July 1, 2008; 36(suppl_2): W70 - W74.
[Abstract] [Full Text] [PDF]


Home page
Nucleic Acids ResHome page
Y.-K. Park, S.-M. Park, Y.-C. Choi, D. Lee, M. Won, and Y. J. Kim
AsiDesigner: exon-based siRNA design server considering alternative splicing
Nucleic Acids Res., July 1, 2008; 36(suppl_2): W97 - W103.
[Abstract] [Full Text] [PDF]


Home page
Nucleic Acids ResHome page
S. Nikolajewa, R. Pudimat, M. Hiller, M. Platzer, and R. Backofen
BioBayesNet: a web server for feature extraction and Bayesian network modeling of biological sequence data
Nucleic Acids Res., July 13, 2007; 35(suppl_2): W688 - W693.
[Abstract] [Full Text] [PDF]


Home page
Nucleic Acids ResHome page
I. Ladunga
More complete gene silencing by fewer siRNAs: transparent optimized design and biophysical signature
Nucleic Acids Res., January 28, 2007; 35(2): 433 - 440.
[Abstract] [Full Text] [PDF]


This Article
Right arrow Abstract Freely available
Right arrow FREE Full Text (Print PDF) Freely available
Right arrow All Versions of this Article:
22/10/1177    most recent
btl024v1
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 ISI Web of Science
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 Search for citing articles in:
ISI Web of Science (8)
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Mückstein, U.
Right arrow Articles by Hofacker, I. L.
Right arrow Search for Related Content
PubMed
Right arrow PubMed Citation
Right arrow Articles by Mückstein, U.
Right arrow Articles by Hofacker, I. L.
Social Bookmarking
 Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?