Asymptotic enumeration of RNA structures with pseudoknots

In this paper, we present the asymptotic enumeration of RNA structures with pseudoknots. We develop a general framework for the computation of exponential growth rate and the asymptotic expansion for the numbers of k-noncrossing RNA structures. Our results are based on the generating function for the number of k-noncrossing RNA pseudoknot structures, S-k(n), derived in Bull. Math. Biol. ( 2008), where k - 1 denotes the maximal size of sets of mutually intersecting bonds. We prove a functional equation for the generating function Sigma S-n >= 0(k)(n)z(n) and obtain for k = 2 and k = 3, the analytic continuation and singular expansions, respectively. It is implicit in our results that for arbitrary k singular expansions exist and via transfer theorems of analytic combinatorics, we obtain asymptotic expression for the coefficients. We explicitly derive the asymptotic expressions for 2- and 3-noncrossing RNA structures. Our main result is the derivation of the formula S-3(n) similar to 10.4724.4!/n(n-1)...(n-4)(5+root 21/2)(n).