# Teaching - counting : number of structures

The number of nested secondary structures that can be formed by an RNA sequence grows
exponentially with sequence length $n$ (about $\sim 1.8^{n}$, see
(Zuker and Sankoff, 1984)).

Zuker and Sankoff presented 1984 a recursion to compute the expected number of admissible structures for an RNA sequence of a given length. The approach applies dynamic programming, i.e. tabularizes results for subproblems.

Here, we use a variant of this algorithm that populates a matrix $C$, where an entry $C_{i,j}$ provides the

Zuker and Sankoff presented 1984 a recursion to compute the expected number of admissible structures for an RNA sequence of a given length. The approach applies dynamic programming, i.e. tabularizes results for subproblems.

Here, we use a variant of this algorithm that populates a matrix $C$, where an entry $C_{i,j}$ provides the

*exact number*of admissible structures for the subsequence from position $i$ to $j$. The overall number of admissible structures for the sequences can be found in the upper right corner $C_{1,n}$, where $n$ denotes the sequence's length and Watson-Crick as well as GU base pairs are considered complementary.RNA sequence $S$:

Minimal loop length $l$:

Recursion for counting the number of possible structures:

$C$ | ||
---|---|---|