Combinatorics of RNA Secondary Structures
Secondary structures of polynucleotides can be view as a certain class of planar vertex-labeled graphs. We construct recursion formulae enumerating various sub-classes of these graphs as well as certain structural elements (sub-graphs). First order asymptotics are derived and their dependence on the logic of base pairing is computed and discussed. Key words. Planar Graphs, Generating Functions, Asymptotic Enumeration, Secondary Structure AMS subject classifications. 05A15, 05A16, 05C30, 92C40 1. Introduction. Presumably the most important problem and the greatest challenge in present day theoretical biophysics deals with deciphering the code that transforms sequences of biopolymers into spatial molecular structures. A sequence is properly visualized as a string of symbols which together with the environment encodes the molecular architecture of the biopolymer. In case of one particular class of biopolymers, the ribonucleic acid (RNA) molecules, decoding of information stored in th...