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.