Asymptotics of canonical and saturated RNA secondary structures.
J Bioinform Comput Biol
; 7(5): 869-93, 2009 Oct.
Article
en En
| MEDLINE
| ID: mdl-19785050
ABSTRACT
It is a classical result of Stein and Waterman that the asymptotic number of RNA secondary structures is 1.104366 . n(-3/2) . 2.618034(n). 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 reduced 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) and that the expected number of base pairs in a canonical secondary structure is 0.31724 . n. The asymptotic number of canonical secondary structures was obtained much earlier by Hofacker, Schuster and Stadler using a different method. 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). Here we show that the asymptotic number of saturated structures is 1.07427 . n(-3/2) . 2.35467(n), the asymptotic expected number of base pairs is 0.337361 . n, and the asymptotic number of saturated stem-loop structures is 0.323954 . 1.69562(n), in contrast to the number 2(n - 2) of (arbitrary) stem-loop structures as classically computed by Stein and Waterman. Finally, we apply the work of Drmota to show that the density of states for [all resp. canonical resp. saturated] secondary structures is asymptotically Gaussian. We introduce a stochastic greedy method to sample random saturated structures, called quasi-random saturated structures, and show that the expected number of base pairs is 0.340633 . n.
Buscar en Google
Colección:
01-internacional
Base de datos:
MEDLINE
Asunto principal:
ARN
/
Biología Computacional
/
Conformación de Ácido Nucleico
Tipo de estudio:
Risk_factors_studies
Idioma:
En
Revista:
J Bioinform Comput Biol
Asunto de la revista:
BIOLOGIA
/
INFORMATICA MEDICA
Año:
2009
Tipo del documento:
Article
País de afiliación:
Estados Unidos