97-03-030
Abstract:
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.