Predicting RNA secondary structures with arbitrary pseudoknots by maximizing the number of stacking pairs

S. Ieong, Ming-Yang Kao, Tak Wah Lam, Wing Kin Sung, Siu Ming Yiu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Citations (Scopus)

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 languageEnglish (US)
Title of host publicationProceedings - 2nd Annual IEEE International Symposium on Bioinformatics and Bioengineering, BIBE 2001
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages183-190
Number of pages8
ISBN (Electronic)0769514235, 9780769514239
DOIs
StatePublished - Jan 1 2001
Event2nd Annual IEEE International Symposium on Bioinformatics and Bioengineering, BIBE 2001 - Bethesda, United States
Duration: Nov 4 2001Nov 6 2001

Publication series

NameProceedings - 2nd Annual IEEE International Symposium on Bioinformatics and Bioengineering, BIBE 2001

Other

Other2nd Annual IEEE International Symposium on Bioinformatics and Bioengineering, BIBE 2001
CountryUnited States
CityBethesda
Period11/4/0111/6/01

Fingerprint

Approximation algorithms
RNA
Polynomials

ASJC Scopus subject areas

  • Biotechnology
  • Computer Science Applications
  • Biomedical Engineering
  • Health Informatics

Cite this

Ieong, S., Kao, M-Y., Lam, T. W., Sung, W. K., & Yiu, S. M. (2001). Predicting RNA secondary structures with arbitrary pseudoknots by maximizing the number of stacking pairs. In Proceedings - 2nd Annual IEEE International Symposium on Bioinformatics and Bioengineering, BIBE 2001 (pp. 183-190). [974428] (Proceedings - 2nd Annual IEEE International Symposium on Bioinformatics and Bioengineering, BIBE 2001). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/BIBE.2001.974428
Ieong, S. ; Kao, Ming-Yang ; Lam, Tak Wah ; Sung, Wing Kin ; Yiu, Siu Ming. / Predicting RNA secondary structures with arbitrary pseudoknots by maximizing the number of stacking pairs. Proceedings - 2nd Annual IEEE International Symposium on Bioinformatics and Bioengineering, BIBE 2001. Institute of Electrical and Electronics Engineers Inc., 2001. pp. 183-190 (Proceedings - 2nd Annual IEEE International Symposium on Bioinformatics and Bioengineering, BIBE 2001).
@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 = "1",
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",

}

Ieong, S, Kao, M-Y, Lam, TW, Sung, WK & Yiu, SM 2001, Predicting RNA secondary structures with arbitrary pseudoknots by maximizing the number of stacking pairs. in Proceedings - 2nd Annual IEEE International Symposium on Bioinformatics and Bioengineering, BIBE 2001., 974428, Proceedings - 2nd Annual IEEE International Symposium on Bioinformatics and Bioengineering, BIBE 2001, Institute of Electrical and Electronics Engineers Inc., pp. 183-190, 2nd Annual IEEE International Symposium on Bioinformatics and Bioengineering, BIBE 2001, Bethesda, United States, 11/4/01. https://doi.org/10.1109/BIBE.2001.974428

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 proceedingConference 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 -

Ieong S, Kao M-Y, Lam TW, Sung WK, Yiu SM. Predicting RNA secondary structures with arbitrary pseudoknots by maximizing the number of stacking pairs. In 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). https://doi.org/10.1109/BIBE.2001.974428