RNA Structures with Pseudo-Knots

Secondary structures of nucleic acids are a particularly interesting class of contact structures. Many important RNA molecules contain pseudo-knots, which are excluded explicitly by the definition of secondary structures. We propose here a generalization of secondary structures that incorporates "non-nested" pseudo-knots. 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 pseudo-knots form a special class of planar graphs. Upper bounds on their number and derived, showing that there are fewer different structures than sequences.