  The paper investigates the computational problem of predicting RNA secondary
structures. The general belief is that allowing pseudoknots makes the problem
hard. Existing polynomial-time algorithms are heuristic algorithms with no
performance guarantee and can only handle limited types of pseudoknots. In this
paper we initiate the study of predicting RNA secondary structures with a
maximum number of stacking pairs while allowing arbitrary pseudoknots. We
obtain two approximation algorithms with worst-case approximation ratios of 1/2
and 1/3 for planar and general secondary structures,respectively. For an RNA
sequence of $n$ bases, the approximation algorithm for planar secondary
structures runs in $O(n^3)$ time while that for the general case runs in linear
time. Furthermore, we prove that allowing pseudoknots makes it NP-hard to
maximize the number of stacking pairs in a planar secondary structure. This
result is in contrast with the recent NP-hard results on psuedoknots which are
based on optimizing some general and complicated energy functions.
