Canonical RNA Pseudoknot Structures

Abstract

In this paper, we study k-noncrossing, σ-canonical RNA pseudoknot structures with minimum arc-length greater or equal to four. Let T_{k, σ}^[4] (n) denote the number of these structures. We derive exact enumeration results by computing the generating function T_{k, σ}^[4] (z) = ∑ _n T_{k, σ}^[4] (n)z ⁿ and derive the asymptotic formulas T_{k, 3}^[4] (n) ∼ c _k n^{−(k−1)2−(k−1/2}) (γ_{k, 3}^[4])⁻ⁿ for k = 3, …, 9. In particular, we have for k = 3, T_{3, 3}^[4] (n) ∼ c₃ n⁻⁵ 2.0348 ⁿ . Our results show that the set of biophysically relevant RNA pseudoknot structures is surprisingly small and suggest a new structure class as target for prediction algorithms.