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 Scopus citations

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

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'Predicting RNA secondary structures with arbitrary pseudoknots by maximizing the number of stacking pairs'. Together they form a unique fingerprint.

  • 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