RNA Structures wth Pseudo-Knots

Peter F. Stadler and Christian Haslinger

Secondary structures of nucleic acids are a particularly interessting 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 sstructures 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 and derived, showing that there are fewer different structures than sequences.

keywords: RNA structure, pseudo-knots, planar graphs, asymptotic enumeration

Return to 1997 working papers list.