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, Sk(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 Sigman>or=0 Sk(n)zn 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 S3(n) approximately 10.4724.4!/n(n-1)...(n-4)(5+[sqrt]21/2)n.
Jin
Emma Y
EY
Center for Combinatorics, LPMC-TJKLC, Nankai University, Tianjin, 300071, People's Republic of China.
Reidys
Christian M
CM
D008433:Mathematics; D008958:Models, Molecular; D009690:Nucleic Acid Conformation; D012313:RNA / Q000737:chemistry*
D012313:RNA