Freiburg RNA Tools
Teaching - hybrid-only

Teaching - hybrid-only : max. intermol. bps

The identification of an optimal RNA-RNA interaction without consideration of intramolecular base pairs can be done efficiently in $O(nm)$ time and space for two RNA sequences $S^{1}$ and $S^{2}$ of lengths $n$ and $m$, resp., (Brian Tjaden et al., 2006). For a Nussinov-like interaction prediction, a dynamic programming table $H$ is filled via the prefix-based recursion
$H_{i,j}=\max\begin{cases} H_{i-1,j-1}+1 & \text{if }S^{1}_{i},S^{2}_{j}\text{ compl. base pair}\\ H_{i-1,j} \\ H_{i,j-1} \\ 0 \end{cases}$,
where an entry $H_{i,j}$ provides the maximal number of intermolecular base pairs for the prefixes $S^{1}_{1..i}$ and $S^{2}_{1..j}$. Note, this recursion is a variant of a local Smith-Waterman (1981) sequence alignment with special scoring, where only Watson-Crick as well as GU base pairs are considered complementary and thus similiar. A traceback from the entry $H_{i,j}$ with the highest value provides an according optimal interaction.

Here, in order to prepare the computation of accessibility-based interaction prediction, the following interval-based recursion is used to identify the RNA-RNA interaction with the maximal number of intermolecular base pairs. To this end, the four-dimensional table $D$ is filled, where an entry $D^{i,k}_{j,l}$ represents the maximal number of base pairs for the sequence intervals $S^{1}_{i..k}$ and $S^{2}_{j..l}$ under the condition that both interval ends are forming the intermolecular base pairs $(S^{1}_{i},S^{2}_{j})$ and $(S^{1}_{k},S^{2}_{l})$.
A list of up to 15 maximal base pair RNA-RNA interactions is provided via exhaustive traceback for all table entries with maximal value, i.e. $D^{i,k}_{j,l}=\max(D)$.
hybrid-only RNA-RNA interaction
RNA sequence $S^{1}$:
RNA sequence $S^{2}$:

Visualization of interacting base pairs (selected structure)

Due to the four-dimensionality of $D$, we only list the optimal hybrid structures (up to 15). On selection, the intermolecular base pairs are visualized.
Possible Structures
The box provides an ASCII representation of the interacting base pairs of the selected structure with $S^{1}$ on top and $S^{2}$ on the bottom. Note, sequence $S^{2}$ is reversed (running from right ($5'$) to left ($3'$)) within this representation. Note further, if no interacting base pairs are present, no visualization is done.