Journal
JOURNAL OF COMPUTATIONAL BIOLOGY
Volume 15, Issue 1, Pages 31-63Publisher
MARY ANN LIEBERT, INC
DOI: 10.1089/cmb.2006.0153
Keywords
enumerative combinatorics; generating functions; RNA secondary structure; RNA shapes
Ask authors/readers for more resources
RNA shapes, introduced by Giegerich et al. (2004), 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 (Steffen et al., 2006; Voss et al., 2006), 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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available