Predicting RNA Secondary Structures with Arbitrary Pseudoknots by Maximizing the Number of Stacking Pairs
<|reference_start|>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 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.<|reference_end|>
@article{ieong2001predicting,
    title={Predicting RNA Secondary Structures with Arbitrary Pseudoknots by
  Maximizing the Number of Stacking Pairs},
    author={Samuel Ieong, Ming-Yang Kao, Tak-Wah Lam, Wing-Kin Sung, Siu-Ming Yiu},
    journal={arXiv preprint arXiv:cs/0111051},
    year={2001},
    archivePrefix={arXiv},
    eprint={cs/0111051},
    primaryClass={cs.CE cs.DS q-bio}
}