Classifying RNA pseudoknotted structures

Computational prediction of the minimum free energy (mfe) secondary structure of an RNA molecule from its base sequence is valuable in understanding the structure and function of the molecule. Since the general problem of predicting pseudoknotted secondary structures is NP-hard, several algorithms have been proposed that find the mfe secondary structure from a restricted class of secondary structures. In this work, we order the algorithms by generality of the structure classes that they handle. We provide simple characterizations of the classes of structures handled by four algorithms, as well as linear time methods to test whether a given secondary structure is in three of these classes. We report on the percentage of biological structures from the PseudoBase and Gutell databases that are handled by these three algorithms. (C) 2003 Published by Elsevier B.V.