@inproceedings{2c1ca49c5af94514b87d75c1d3ebf58b,
title = "Predicting RNA secondary structures with arbitrary pseudoknots by maximizing the number of stacking pairs",
abstract = "In this paper we investigate the computational problem of predicting RNA secondary structures that allow any kinds of pseudoknots. The general belief is that allowing pseudoknots makes the problem very difficult. Existing polynomial-time algorithms, which aim at structures that optimize some energy functions, can only handle a certain types of pseudoknots. In this paper we initiate the study of approximation algorithms for handling all kinds of pseudoknots. We focus on predicting RNA secondary structures with a maximum number of stacking pairs and obtain two approximation algorithms with worst-case approximation ratios of 1/2 and 1/3 for planar and general secondary structures, respectively. Furthermore, we prove that allowing pseudoknots would make the problem of maximizing the number of stacking pairs on planar secondary structure to be NP-hard. This result should be contrasted with the recent NP-hard results on psuedoknots which are based on optimizing some peculiar energy functions.",
author = "S. Ieong and Ming-Yang Kao and Lam, {Tak Wah} and Sung, {Wing Kin} and Yiu, {Siu Ming}",
year = "2001",
month = jan,
day = "1",
doi = "10.1109/BIBE.2001.974428",
language = "English (US)",
series = "Proceedings - 2nd Annual IEEE International Symposium on Bioinformatics and Bioengineering, BIBE 2001",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "183--190",
booktitle = "Proceedings - 2nd Annual IEEE International Symposium on Bioinformatics and Bioengineering, BIBE 2001",
address = "United States",
note = "2nd Annual IEEE International Symposium on Bioinformatics and Bioengineering, BIBE 2001 ; Conference date: 04-11-2001 Through 06-11-2001",
}