Asymptotics of canonical RNA secondary structures
It is a classical result of Stein and Waterman  that the asymptotic number S(n) of RNA secondary structures is 1.104366·n -3/2·2.618034n, where the combinatorial model of RNA concerns a length n homopolymer, such that any base can pair with any other base, subject to the usual convention that hairpin loops must contain at least θ = 1 unpaired bases. The result of Stein and Waterman is proved by developing recursions, using generating functions and applying Bender's theorem . These recursions form the basis to compute the minimum free energy secondary structure for a given RNA sequence, with respect to the Nussinov energy model , later extended by Zuker  to substantially more complicated resursions for the Turner nearest neighbor energy model . In this paper, we study combinatorial asymptotics for two special subclasses of RNA secondary structures - canonical and saturated structures. Canonical secondary structures are defined to have no lonely (isolated) base pairs. This class of secondary structures was introduced by Bompfünewerer et al. , who noted that the run time of Vienna RNA Package is substantially decreased when restricting computations to canonical structures. Here we provide an explanation for the speed-up, by proving that the asymptotic number of canonical RNA secondary structures is 2.1614·n-3/2·1.96798 n. Saturated secondary structures have the property that no base pairs can be added without violating the definition of secondary structure (i.e. introducing a pseudoknot or base triple). In the Nussinov energy model, where the energy for a base pair is -1, saturated structures  correspond to kinetic traps. In , we showed that the asymptotic number of saturated structures of a length n homopolymer is 1.07427·n-3/2·2.35467 n. In this paper, we show that the expected number of base pairs of random saturated structures, generated by a natural stochastic procedure, is zθ+1/(1 - z)2 e(-z-∑i=0θzi/i+1) (∫e(z+∑i=0θzi/i+1)dz).
|Conference||2009 9th IEEE International Conference on Bioinformatics and BioEngineering, BIBE 2009|
Clote, P. (Peter), Kranakis, E, & Krizanc, D. (Danny). (2009). Asymptotics of canonical RNA secondary structures. Presented at the 2009 9th IEEE International Conference on Bioinformatics and BioEngineering, BIBE 2009. doi:10.1109/BIBE.2009.76