# Teaching - Nussinov : structure with max. #bp

The algorithm by
Ruth Nussinov et al. (1978)
computes for a given
RNA sequence the maximal number of base pairs of any nested structure.
To this end, dynamic programming is applied, which also enables the
identification of an according maximally base paired structure via traceback.

Here, we provide different recursions to 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 position $i$ to $j$. The entry $D_{1,n}$ provides the overall maximal number of base pairs for the whole sequence of length $n$. Watson-Crick as well as GU base pairs are considered complementary.

Furthermore, beside the identification of an according optimal structure via traceback, we provide an exhaustive enumeration of up to 15 suboptimal structures using the algorithm by Stefan Wuchty et al. (1999).

For each structure, the according traceback is visualized. Note, for recursions implementing an ambiguous decomposition different tracebacks might yield the same structure. These will be listed several times, once for each traceback.

Here, we provide different recursions to 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 position $i$ to $j$. The entry $D_{1,n}$ provides the overall maximal number of base pairs for the whole sequence of length $n$. Watson-Crick as well as GU base pairs are considered complementary.

Furthermore, beside the identification of an according optimal structure via traceback, we provide an exhaustive enumeration of up to 15 suboptimal structures using the algorithm by Stefan Wuchty et al. (1999).

For each structure, the according traceback is visualized. Note, for recursions implementing an ambiguous decomposition different tracebacks might yield the same structure. These will be listed several times, once for each traceback.

RNA sequence $S$:

Minimal loop length $l$:

Delta #bp to maximum:

Recursion to be used:

Possible Structures |
---|

Select a structure from the list or (multiple times) a cell of $D$
to see according tracebacks. Note, the structure list is limited to
the first 15 structures identified via traceback and thus depends
on the recursion case order.

Below, we provide a graphical depiction of the selected structure. Note, the rendering does not support a minimal loop length of 0.

Below, we provide a graphical depiction of the selected structure. Note, the rendering does not support a minimal loop length of 0.

Visualization done with
forna.
Base pairs are given by red edges, the sequence backbone is given by
gray edges.