To predict RNA-RNA interactions optimizing both intra- as well as intermolecular base pairs one can use a so called co-folding approach. Here, the two interacting sequences are concatenated (using a non-pairing linker sequence) to a single pseudo-sequence that is then folded via single structure prediction. When using a full nearest-neighbor energy model, special care has to be taken for the scoring of the loop containing the linker as discussed by Ivo L. Hofacker and coworkers (1994).

Here, we extend the Nussinov algorithm for such a co-folding scheme. No special linker treatment is necessary, since we do a base pair maximization without taking the base pair's context into account. We can directly use the Nussinov algorithm without any extensions when using a linker sequence of length $l+1$ ($L=\text{X}_{1}..\text{X}_{l+1}$), where $l$ denotes the minimal loop length. The linker's length enables intermolecular base pairs between the concatenated sequence ends. Thus, for two sequences $S^{1}$ and $S^{2}$, the hybrid sequence used for folding is given by $S=S^{1}LS^{2}$.

For prediction, we fill the dynamic programming table $D$, where an entry $D_{i,j}$ provides the maximal number of base pairs of any nested structure for the subsequence from $S_{i}$ to $S_{j}$. The entry $D_{1,n}$ provides the overall maximal number of base pairs for the whole hybrid sequence $S$ of length $n=|S^{1}|+l+1+|S^{2}|$. Watson-Crick as well as GU base pairs are considered complementary.
Beside the identification of an according optimal hybrid structure via traceback (intra- and intermolecular base pairs are given by $()$ and $[\;]$, resp.), we provide an exhaustive enumeration of up to 15 suboptimal hybrids using the algorithm by Stefan Wuchty et al. (1999). For each structure, the according traceback is visualized on selection.