Freiburg RNA Tools
Teaching - counting

# 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 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: