2026-07-072026-07-07http://salesiana.dossiersoluciones.com/handle/123456789/30928The 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.A preliminary version of this work appeared in Proceedings of the IEEE International Symposium on Bio-Informatics & Biomedical Engineering (BIBE 2001), Washington, DC, 2001Computational Engineering, Finance, and ScienceData Structures and AlgorithmsQuantitative BiologyF2.2; G2.3; J.3text