Combinatorial design of pseudoknot RNA

Abstract: In this paper we enumerate k-noncrossing RNA pseudoknot structures with given minimum stack-length, σ. One main result of the paper is the asymptotic formula for their number: , where is explicitly known. Our results show that the number of k-noncrossing structures without isolated base pairs is significantly smaller than the number of all k-noncrossing structures. In particular we prove that, for large n, the number of 3- and 4-noncrossing RNA structures with stack-length ⩾2 is given by and , respectively. Our results are of importance for prediction algorithms and provide evidence for the existence of neutral networks of RNA pseudoknot structures. [Copyright &y& Elsevier]