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 - Jan 1 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 | United States |
| City | Bethesda |
| Period | 11/4/01 → 11/6/01 |
Fingerprint
ASJC Scopus subject areas
- Biotechnology
- Computer Science Applications
- Biomedical Engineering
- Health Informatics
Cite this
}
Predicting RNA secondary structures with arbitrary pseudoknots by maximizing the number of stacking pairs. / Ieong, S.; Kao, Ming-Yang; Lam, Tak Wah; Sung, Wing Kin; Yiu, Siu Ming.
Proceedings - 2nd Annual IEEE International Symposium on Bioinformatics and Bioengineering, BIBE 2001. Institute of Electrical and Electronics Engineers Inc., 2001. p. 183-190 974428 (Proceedings - 2nd Annual IEEE International Symposium on Bioinformatics and Bioengineering, BIBE 2001).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
TY - GEN
T1 - Predicting RNA secondary structures with arbitrary pseudoknots by maximizing the number of stacking pairs
AU - Ieong, S.
AU - Kao, Ming-Yang
AU - Lam, Tak Wah
AU - Sung, Wing Kin
AU - Yiu, Siu Ming
PY - 2001/1/1
Y1 - 2001/1/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84960927813&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84960927813&partnerID=8YFLogxK
U2 - 10.1109/BIBE.2001.974428
DO - 10.1109/BIBE.2001.974428
M3 - Conference contribution
AN - SCOPUS:84960927813
T3 - Proceedings - 2nd Annual IEEE International Symposium on Bioinformatics and Bioengineering, BIBE 2001
SP - 183
EP - 190
BT - Proceedings - 2nd Annual IEEE International Symposium on Bioinformatics and Bioengineering, BIBE 2001
PB - Institute of Electrical and Electronics Engineers Inc.
ER -