Please use this identifier to cite or link to this item: https://doi.org/10.1089/106652703322756186
Title: Predicting RNA Secondary Structures with Arbitrary Pseudoknots by Maximizing the Number of Stacking Pairs
Authors: Ieong, S.
Kao, M.-Y.
Lam, T.-W.
Sung, W.-K. 
Yiu, S.-M.
Keywords: Approximation algorithms
Computational complexity
Pseudoknots
RNA secondary structures
Stacking pairs
Issue Date: 2003
Source: Ieong, S., Kao, M.-Y., Lam, T.-W., Sung, W.-K., Yiu, S.-M. (2003). Predicting RNA Secondary Structures with Arbitrary Pseudoknots by Maximizing the Number of Stacking Pairs. Journal of Computational Biology 10 (6) : 981-995. ScholarBank@NUS Repository. https://doi.org/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(n3) 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.
Source Title: Journal of Computational Biology
URI: http://scholarbank.nus.edu.sg/handle/10635/39233
ISSN: 10665277
DOI: 10.1089/106652703322756186
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

37
checked on Dec 11, 2017

WEB OF SCIENCETM
Citations

25
checked on Dec 11, 2017

Page view(s)

49
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.