Open AccessPseudoknots in RNA Secondary Structures
Author(s) -
Rune B. Lyngsø,
Christian N. S. Pedersen
Publication year - 2000
Publication title -
brics report series
Language(s) - English
Resource type - Journals
eISSN - 1601-5355
pISSN - 0909-0878
DOI - 10.7146/brics.v7i1.20129
Subject(s) - rna , nucleic acid secondary structure , protein secondary structure , time complexity , sequence (biology) , computational biology , nucleic acid structure , algorithm , computer science , mathematics , class (philosophy) , theoretical computer science , biology , genetics , artificial intelligence , gene , biochemistry
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 satisfactorily 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 O(n^5) and space O(n^3) predicts the secondary structure of an RNA sequence of length n 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.