Mathematics – Combinatorics
Scientific paper
2011-12-20
Mathematics
Combinatorics
17 pages
Scientific paper
It is a classical result of Stein and Waterman that the asymptotic number of RNA secondary structures is $1.104366 \cdot n^{-3/2} \cdot 2.618034^n$. To provide a better understanding of the kinetics of RNA secondary structure formation, we are interested in determining the asymptotic number of secondary structures that are {\em locally optimal}, with respect to a particular energy model. In the Nussinov energy model, where each base pair contributes -1 towards the energy of the structure, locally optimal structures are exactly the {\em saturated} structures, for which we have previously shown that asymptotically, there are $1.07427\cdot n^{-3/2} \cdot 2.35467^n$ many saturated structures for a sequence of length $n$. In this paper, we consider the {\em base stacking energy model}, a mild variant of the Nussinov model, where each stacked base pair contributes -1 toward the energy of the structure. Locally optimal structures with respect to the base stacking energy model are exactly those secondary structures, whose stems cannot be extended. Such structures were first considered by Evers and Giegerich, who described a dynamic programming algorithm to enumerate all locally optimal structures. In this paper, we apply methods from enumerative combinatorics to compute the asymptotic number of such structures.
Clote Peter
Fusy Eric
No associations
LandOfFree
Combinatorics of locally optimal RNA secondary structures does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Combinatorics of locally optimal RNA secondary structures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Combinatorics of locally optimal RNA secondary structures will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-55892