Combinatorics of RNA Secondary Structures and Related Problems

Abstract

We derive expressions for the asymptotic number of RNA secondary structures satisfying a variety of constraints. We also discuss the asymptotics of the expected number of base pairs in randomly chosen structures, again, under different constraints. Finally, we relate these results to problems arising in the analysis of algorithms.