Asymptotics of RNA shapes

William Andrew Lorenz 1 Peter Clote 1 Yann Ponty 2, 3
2 AMIB - Algorithms and Models for Integrative Biology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, Polytechnique - X, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : RNA shapes, introduced by Giegerich et al., provide a useful classification of the branching complexity for RNA secondary structures. In this paper, we derive an exact value for the asymptotic number of RNA shapes, by relying on an elegant relation between non-ambiguous, context-free grammars and generating functions. Our results provide a theoretical upper bound on the length of RNA sequences amenable to probabilistic shape analysis, under the assumption that any base can basepair with any other base. Since the relation between context-free grammars and asymptotic enumeration is simple yet not well-known in bioinformatics, we give a self-contained presentation with illustrative examples. Additionally, we prove a surprising 1-to-1 correspondence between Pi-shapes and Motzkin numbers
Type de document :
Article dans une revue
Journal of Computational Biology, Mary Ann Liebert, 2008, 15 (1), pp.31--63. 〈10.1089/cmb.2006.0153〉
Liste complète des métadonnées
Contributeur : Yann Ponty <>
Soumis le : lundi 20 décembre 2010 - 16:39:42
Dernière modification le : vendredi 23 février 2018 - 13:45:16




William Andrew Lorenz, Peter Clote, Yann Ponty. Asymptotics of RNA shapes. Journal of Computational Biology, Mary Ann Liebert, 2008, 15 (1), pp.31--63. 〈10.1089/cmb.2006.0153〉. 〈inria-00548861〉



Consultations de la notice