Predicting RNA secondary structures with arbitrary pseudoknots by maximizing the number of stacking pairs.
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.
Ieong
Samuel
S
Department of Computer Science, Yale University, New Haven, CT 06520, USA.
Kao
Ming-Yang
MY
Lam
Tak-Wah
TW
Sung
Wing-Kin
WK
Yiu
Siu-Ming
SM
D000465:Algorithms; D020029:Base Pairing; D001483:Base Sequence; D019295:Computational Biology / Q000379:methods*; D008969:Molecular Sequence Data; D009690:Nucleic Acid Conformation; D012313:RNA / Q000737:chemistry* / Q000235:genetics
D012313:RNA