Predicting RNA secondary structures with arbitrary pseudoknots by maximizing the number of stacking pairs. |
| |
Authors: | Samuel Ieong Ming-Yang Kao Tak-Wah Lam Wing-Kin Sung Siu-Ming Yiu |
| |
Institution: | Department of Computer Science, Yale University, New Haven, CT 06520, USA. |
| |
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. |
| |
Keywords: | |
|
|