Predicting RNA secondary structures with arbitrary pseudoknots by maximizing the number of stacking pairs

J Comput Biol. 2003;10(6):981-95. doi: 10.1089/106652703322756186.

Abstract

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 handle only 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.

MeSH terms

  • Algorithms
  • Base Pairing
  • Base Sequence
  • Computational Biology / methods*
  • Molecular Sequence Data
  • Nucleic Acid Conformation*
  • RNA / chemistry*
  • RNA / genetics

Substances

  • RNA