Abstract:
RNA molecules are sequences of nucleotides that serve as more
than mere intermediaries between DNA and proteins, e.g. as catalytic
molecules. Computational prediction of RNA secondary structure is among the
few structure prediction problems that can be solved satisfactory in
polynomial time. Most work has been done to predict structures that do not
contain pseudoknots. Allowing pseudoknots introduce modelling and
computational problems. In this paper we consider the problem of predicting
RNA secondary structure when certain types of pseudoknots are allowed. We
first present an algorithm that in time 
and space 
predicts
the secondary structure of an RNA sequence of length 
in a model that
allows certain kinds of pseudoknots. We then prove that the general problem
of predicting RNA secondary structure containing pseudoknots is
NP-complete for a large class of reasonable models of
pseudoknots.
and space predicts
the secondary structure of an RNA sequence of length in a model that
allows certain kinds of pseudoknots. We then prove that the general problem
of predicting RNA secondary structure containing pseudoknots is
NP-complete for a large class of reasonable models of
pseudoknots.Available as PostScript, PDF, DVI.