Target prediction and a statistical sampling algorithm for RNA-RNA interaction

Abstract

Motivation: It has been proven that the accessibility of the target sites has a critical influence on RNA-RNA binding, in general and the specificity and efficiency of miRNAs and siRNAs, in particular. Recently, O(N(6)) time and O(N(4)) space dynamic programming (DP) algorithms have become available that compute the partition function of RNA-RNA interaction complexes, thereby providing detailed insights into their thermodynamic properties.

Results: Modifications to the grammars underlying earlier approaches enables the calculation of interaction probabilities for any given interval on the target RNA. The computation of the 'hybrid probabilities' is complemented by a stochastic sampling algorithm that produces a Boltzmann weighted ensemble of RNA-RNA interaction structures. The sampling of k structures requires only negligible additional memory resources and runs in O(k.N(3)).

Availability: The algorithms described here are implemented in C as part of the rip package. The source code of rip2 can be downloaded from http://www.combinatorics.cn/cbpc/rip.html and http://www.bioinf.uni-leipzig.de/Software/rip.html.

Supplementary information: Supplementary data are available at Bioinformatics online.

Fig. 1.

Examples of RNA-RNA interactions structures. The primary interaction region(s) are highlighted in grey in the experimentally supported structural models from the literature: (A) ompA-MicA: (Udekwu et al., 2005); (B) sodB-RyhB: (Geissmann and Touati, 2004); (C) fhlA-OxyS: (Argaman and Altuvia, 2000). Hybridization probabilities computed by rip2 are annotated by black boxes for regions with a probability larger than 10%. In many cases, the computational predictions identify additional hybridization regions that may further stabilize the interaction.

Fig. 2.

(A) A zigzag, generated by R₂S₁, R₃S₃ and R₅S₄. (B) We partition the joint structure J_1,24;1,23 in segments and tight structures.

Fig. 3.

The four basic types of TS. (A) ○ : {R_iS_h} = J_i,j;h,ℓ and i = j, h = ℓ; (B) ▽ : R_iR_j ∈ J_i,j;h,ℓ and S_hS_ℓ ∉ J_i,j;h,ℓ; (C) □ : {R_iR_j, S_hS_ℓ} ∈ J_i,j;h,ℓ; (D) △ : S_hS_ℓ ∈ J_i,j;h,ℓ and R_iR_j ∉ J_i,j;h,ℓ.

Fig. 4.

Illustration of the reduction of arbitrary joint structures and of right-tight structures, Procedure (a), and of tight structures, Procedure (b). In the bottom row the symbols for the 10 distinct types of structural components are listed: A, B maximal secondary structure segments R[i, j], S[r, s]; C arbitrary joint structure J_1,N;1,M; D right-tight structures J^RT_i,j;r,s; E double-tight structure J^DT_i,j;r,s; F tight structure of type ▽, △ or □; G type □ tight structure J^□_i,j;r,s; H type ▽ tight structure J^▽_i,j;r,s; J type △ tight structure J^△_i,j;r,s; K hybrid structure J^Hy_i,j;h,ℓ; L substructure of a hybrid J^h_i,j;h,ℓ such that R_iS_j and R_hS_ℓ are exterior arcs and J^h_i,j;h,ℓ itself is not a hybrid since it is not maximal; M isolated segment R[i, j] or S[h, ℓ].

Fig. 5.

Different grammars lead to different (parse) trees. We show the parse tree T_J1,11;1,11 for the same joint structure J_1,11;1,11 according to the grammars of rip2 (A) and rip1 (B), respectively.

Fig. 6.

Decomposition of J^DT,KKB_i,j;h,ℓ (l.h.s.) and J^RT,KKA_i,j;h,ℓ (r.hs.).

Fig. 7.

Hybrid probability: the maximality of hybrids implies that—although the intervals [h₁, ℓ₁] and [h₂, ℓ₂] overlap—they belong to two distinct hybrids (gray).

Fig. 8.

Stochastic backtracing algorithm: elements of stack 𝒜 are successively decomposed according to the hybrid-grammar. The resulting arcs and unpaired vertices are stored in the list ℒ which, once 𝒜 is empty, eventually contains the Boltzmann-sampled interaction structure.

Fig. 9.

Interaction of sodB–RhyB. (A) Base-pairing probability matrix. The upper right triangle shows the probabilities obtained from the exact backwards recursion, the lower left triangle is the estimate from a sample of 10 000 structures obtained by stochastic backtracing, showing that the estimates converge quickly. (B) Comparison of the structure proposed in Geissmann and Touati (2004) and the rip2 prediction. While the major stable hairpins agree and rip2 correctly predicts the primary interaction region, rip2 also identifies additional interaction regions that may stabilize the interaction. (C) Sampled joint structures (here the 20 most frequent ones) are represented as dot-bracket strings: () and [] represent pairs of interior and exterior arc, respectively, while dots indicate unpaired bases. | separates the two RNA sequences which are both written in 5^′ → 3^′ direction.

Fig. 10.

Interaction maps. The ompA–MicA interaction (A) has a dominating interaction region that brings together the 3^′ end of ompA and the 5^′ terminus of MicA. The sodB–RhyB interactions (B) has two clear hybridization regions in the middle of the molecules and a diffuse contact area at the 3^′ end of sodB. The grayscale show the probabilities π_ik. Tick marks indicate every 10th nucleotide. The correlations between the major binding regions can be computed easily from Boltzmann samples. The heatmaps show the correlation coefficients for the most probable interaction regions (indicated by numbers in the interaction maps). (C) For sodB–RhyB, we observe fairly weak correlations, except for the cooperative interaction between contacts 3 and 4. In case of ompA–MicA, we observe strong negative correlations between conflicting hybridization regions.