RNA-LEGO: Combinatorial Design of Pseudoknot RNA

Abstract

In this paper we enumerate $k$-noncrossing RNA pseudoknot structures with given minimum stack-length. We show that the numbers of $k$-noncrossing structures without isolated base pairs are significantly smaller than the number of all $k$-noncrossing structures. In particular we prove that the number of 3- and 4-noncrossing RNA structures with stack-length $\ge 2$ is for large $n$ given by $311.2470\frac{4!}{n(n-1)...(n-4)}2.5881^n$ and $1.217\cdot 10^7{n}^{-21/2}3.0382^n$, respectively. We furthermore show that for $k$-noncrossing RNA structures the drop in exponential growth rates between the number of all structures and the number of all structures with stack-size $\ge 2$ increases significantly. Our results are of importance for prediction algorithms for pseudoknot-RNA and provide evidence that there exist neutral networks of RNA pseudoknot structures.

21 pages and 8 figures

Cited by in corpus (5)

• Canonical RNA pseudoknot structures
• Folding 3-noncrossing RNA pseudoknot structures
• Stacks in canonical RNA pseudoknot structures
• Pseudoknot RNA structures with arc-length $\ge 4$
• $k$-noncrossing RNA structures with arc-length $\ge 3$