File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Predicting RNA Secondary Structures with Arbitrary Pseudoknots by Maximizing the Number of Stacking Pairs

TitlePredicting RNA Secondary Structures with Arbitrary Pseudoknots by Maximizing the Number of Stacking Pairs
Authors
KeywordsApproximation algorithms
Computational complexity
Pseudoknots
RNA secondary structures
Stacking pairs
Issue Date2003
PublisherMary Ann Liebert, Inc Publishers. The Journal's web site is located at http://www.liebertpub.com/cmb
Citation
Journal Of Computational Biology, 2003, v. 10 n. 6, p. 981-995 How to Cite?
AbstractThe paper investigates the computational problem of predicting RNA secondary structures. The general belief is that allowing pseudoknots makes the problem hard. Existing polynomial-time algorithms are heuristic algorithms with no performance guarantee and can handle only limited types of pseudoknots. In this paper, we initiate the study of predicting RNA secondary structures with a maximum number of stacking pairs while allowing arbitrary pseudoknots. We obtain two approximation algorithms with worst-case approximation ratios of 1/2 and 1/3 for planar and general secondary structures, respectively. For an RNA sequence of n bases, the approximation algorithm for planar secondary structures runs in O(n3) time while that for the general case runs in linear time. Furthermore, we prove that allowing pseudoknots makes it NP-hard to maximize the number of stacking pairs in a planar secondary structure. This result is in contrast with the recent NP-hard results on psuedoknots which are based on optimizing some general and complicated energy functions.
Persistent Identifierhttp://hdl.handle.net/10722/88933
ISSN
2023 Impact Factor: 1.4
2023 SCImago Journal Rankings: 0.659
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorIeong, Sen_HK
dc.contributor.authorKao, MYen_HK
dc.contributor.authorLam, TWen_HK
dc.contributor.authorSung, WKen_HK
dc.contributor.authorYiu, SMen_HK
dc.date.accessioned2010-09-06T09:50:18Z-
dc.date.available2010-09-06T09:50:18Z-
dc.date.issued2003en_HK
dc.identifier.citationJournal Of Computational Biology, 2003, v. 10 n. 6, p. 981-995en_HK
dc.identifier.issn1066-5277en_HK
dc.identifier.urihttp://hdl.handle.net/10722/88933-
dc.description.abstractThe paper investigates the computational problem of predicting RNA secondary structures. The general belief is that allowing pseudoknots makes the problem hard. Existing polynomial-time algorithms are heuristic algorithms with no performance guarantee and can handle only limited types of pseudoknots. In this paper, we initiate the study of predicting RNA secondary structures with a maximum number of stacking pairs while allowing arbitrary pseudoknots. We obtain two approximation algorithms with worst-case approximation ratios of 1/2 and 1/3 for planar and general secondary structures, respectively. For an RNA sequence of n bases, the approximation algorithm for planar secondary structures runs in O(n3) time while that for the general case runs in linear time. Furthermore, we prove that allowing pseudoknots makes it NP-hard to maximize the number of stacking pairs in a planar secondary structure. This result is in contrast with the recent NP-hard results on psuedoknots which are based on optimizing some general and complicated energy functions.en_HK
dc.languageengen_HK
dc.publisherMary Ann Liebert, Inc Publishers. The Journal's web site is located at http://www.liebertpub.com/cmben_HK
dc.relation.ispartofJournal of Computational Biologyen_HK
dc.subjectApproximation algorithms-
dc.subjectComputational complexity-
dc.subjectPseudoknots-
dc.subjectRNA secondary structures-
dc.subjectStacking pairs-
dc.subject.meshAlgorithmsen_HK
dc.subject.meshBase Pairingen_HK
dc.subject.meshBase Sequenceen_HK
dc.subject.meshComputational Biology - methodsen_HK
dc.subject.meshMolecular Sequence Dataen_HK
dc.subject.meshNucleic Acid Conformationen_HK
dc.subject.meshRNA - chemistry - geneticsen_HK
dc.titlePredicting RNA Secondary Structures with Arbitrary Pseudoknots by Maximizing the Number of Stacking Pairsen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1066-5277&volume=10&issue=6&spage=981&epage=995&date=2003&atitle=Predicting+RNA+Secondary+Structures+with+Arbitrary+Pseudoknots+by+Maximizing+the+Number+of+Stacking+Pairsen_HK
dc.identifier.emailLam, TW:twlam@cs.hku.hken_HK
dc.identifier.emailYiu, SM:smyiu@cs.hku.hken_HK
dc.identifier.authorityLam, TW=rp00135en_HK
dc.identifier.authorityYiu, SM=rp00207en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1089/106652703322756186en_HK
dc.identifier.pmid14980021-
dc.identifier.scopuseid_2-s2.0-0742286998en_HK
dc.identifier.hkuros91595en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0742286998&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume10en_HK
dc.identifier.issue6en_HK
dc.identifier.spage981en_HK
dc.identifier.epage995en_HK
dc.identifier.isiWOS:000188455100010-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridIeong, S=10241850300en_HK
dc.identifier.scopusauthoridKao, MY=7202198147en_HK
dc.identifier.scopusauthoridLam, TW=7202523165en_HK
dc.identifier.scopusauthoridSung, WK=13310059700en_HK
dc.identifier.scopusauthoridYiu, SM=7003282240en_HK
dc.identifier.issnl1066-5277-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats