RNA Structures with Pseudo-Knots - Graph-Theoretical and Combinatorial Properties

Secondary structures of nucleic acids are a particularly interesting class of contact structures. Many important RNA molecules contain pseudoknots, which are excluded explicitly by the definition of secondary structures. We propose here a generalization of secondary structures that incorporates "non-nested" pseudoknots. We also introduce a measure for the complexity of more general contact structures in terms of the chromatic number of their intersection graph. We show that RNA structures without nested pseudoknots form a special class of planar graphs. Upper bounds on their number are derived, showing that there are fewer different structures than sequences. 1. Introduction Presumably the most important problem and the greatest challenge in present day theoretical biophysics is 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 molecul..