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.
Original language | English (US) |
---|---|
Title of host publication | Proceedings - 2nd Annual IEEE International Symposium on Bioinformatics and Bioengineering, BIBE 2001 |
Publisher | Institute of Electrical and Electronics Engineers Inc. |
Pages | 183-190 |
Number of pages | 8 |
ISBN (Electronic) | 0769514235, 9780769514239 |
DOIs | |
State | Published - 2001 |
Event | 2nd Annual IEEE International Symposium on Bioinformatics and Bioengineering, BIBE 2001 - Bethesda, United States Duration: Nov 4 2001 → Nov 6 2001 |
Publication series
Name | Proceedings - 2nd Annual IEEE International Symposium on Bioinformatics and Bioengineering, BIBE 2001 |
---|
Other
Other | 2nd Annual IEEE International Symposium on Bioinformatics and Bioengineering, BIBE 2001 |
---|---|
Country/Territory | United States |
City | Bethesda |
Period | 11/4/01 → 11/6/01 |
ASJC Scopus subject areas
- Biotechnology
- Computer Science Applications
- Biomedical Engineering
- Health Informatics