Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics

Reeder J, Giegerich R (2004)
BMC Bioinformatics 5(1).

Download
OA
Journal Article | Published | English
Author
;
Abstract
Background: The general problem of RNA secondary structure prediction under the widely used thermodynamic model is known to be NP-complete when the structures considered include arbitrary pseudoknots. For restricted classes of pseudoknots, several polynomial time algorithms have been designed, where the O(n6)time and O(n4) space algorithm by Rivas and Eddy is currently the best available program. Results: We introduce the class of canonical simple recursive pseudoknots and present an algorithm that requires O(n4) time and O(n2) space to predict the energetically optimal structure of an RNA sequence, possible containing such pseudoknots. Evaluation against a large collection of known pseudoknotted structures shows the adequacy of the canonization approach and our algorithm. Conclusions: RNA pseudoknots of medium size can now be predicted reliably as well as efficiently by the new algorithm.
Publishing Year
ISSN
PUB-ID

Cite this

Reeder J, Giegerich R. Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics. BMC Bioinformatics. 2004;5(1).
Reeder, J., & Giegerich, R. (2004). Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics. BMC Bioinformatics, 5(1).
Reeder, J., and Giegerich, R. (2004). Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics. BMC Bioinformatics 5.
Reeder, J., & Giegerich, R., 2004. Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics. BMC Bioinformatics, 5(1).
J. Reeder and R. Giegerich, “Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics”, BMC Bioinformatics, vol. 5, 2004.
Reeder, J., Giegerich, R.: Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics. BMC Bioinformatics. 5, (2004).
Reeder, Jens, and Giegerich, Robert. “Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics”. BMC Bioinformatics 5.1 (2004).
Main File(s)
Access Level
OA Open Access

This data publication is cited in the following publications:
This publication cites the following data publications:

94 Citations in Europe PMC

Data provided by Europe PubMed Central.

Thermodynamic matchers for the construction of the cuckoo RNA family.
Reinkensmeier J, Giegerich R., RNA Biol 12(2), 2015
PMID: 25779873
Secondary Structure Predictions for Long RNA Sequences Based on Inversion Excursions and MapReduce.
Yehdego DT, Zhang B, Kodimala VK, Johnson KL, Taufer M, Leung MY., IEEE Int Symp Parallel Distrib Process Workshops Phd Forum 2013(), 2013
PMID: 26023357
A Tool Preference Choice Method for RNA Secondary Structure Prediction by SVM with Statistical Tests.
Hor CY, Yang CB, Chang CH, Tseng CT, Chen HH., Evol. Bioinform. Online 9(), 2013
PMID: 23641141
On the combinatorics of sparsification.
Huang FW, Reidys CM., Algorithms Mol Biol 7(1), 2012
PMID: 23088372
Identifying complete RNA structural ensembles including pseudoknots.
Gupta A, Rahman R, Li K, Gribskov M., RNA Biol 9(2), 2012
PMID: 22418849
On the page number of RNA secondary structures with pseudoknots.
Clote P, Dobrev S, Dotu I, Kranakis E, Krizanc D, Urrutia J., J Math Biol 65(6-7), 2012
PMID: 22159642
Thermodynamic heuristics with case-based reasoning: combined insights for RNA pseudoknot secondary structure.
Al-Khatib RM, Rashid NA, Abdullah R., J. Biomol. Struct. Dyn. 29(1), 2011
PMID: 21696223
K-partite RNA secondary structures.
Jiang M, Tejada PJ, Lasisi RO, Cheng S, Fechser DS., J. Comput. Biol. 17(7), 2010
PMID: 20632871
A comparative taxonomy of parallel algorithms for RNA secondary structure prediction.
Al-Khatib RM, Abdullah R, Rashid NA., Evol. Bioinform. Online 6(), 2010
PMID: 20458364
Approximation algorithms for predicting RNA secondary structures with arbitrary pseudoknots.
Jiang M., IEEE/ACM Trans Comput Biol Bioinform 7(2), 2010
PMID: 20431151
RNA secondary structure prediction using a self-consistent mean field approach.
Kleesiek J, Torda AE., J Comput Chem 31(6), 2010
PMID: 19899145
Introduction to special issue on RNA.
Clote P., J Math Biol 56(1-2), 2008
PMID: 17938928

36 References

Data provided by Europe PubMed Central.

An approximation of loop free energy values of RNA H-pseudoknots.
Gultyaev AP, van Batenburg FH, Pleij CW., RNA 5(5), 1999
PMID: 10334330
Linguistic approaches to biological sequences.
Searls DB., Comput. Appl. Biosci. 13(4), 1997
PMID: 9283748
A grammar-based unification of several alignment and folding algorithms
Lefebvre F., 1996
Reducing the conformation space in RNA structure prediction
Evers D, Giegerich R., 2001
Bielefeld Bioinformatics Server
AUTHOR UNKNOWN, 0
Crystal structure of a hepatitis delta virus ribozyme.
Ferre-D'Amare AR, Zhou K, Doudna JA., Nature 395(6702), 1998
PMID: 9783582
RnaViz 2: an improved representation of RNA secondary structure.
De Rijk P, Wuyts J, De Wachter R., Bioinformatics 19(2), 2003
PMID: 12538259
RNA pseudoknots that inhibit human immunodeficiency virus type 1 reverse transcriptase.
Tuerk C, MacDougal S, Gold L., Proc. Natl. Acad. Sci. U.S.A. 89(15), 1992
PMID: 1379730
Five pseudoknots are present at the 204 nucleotides long 3' noncoding region of tobacco mosaic virus RNA
van A, Abrahams JP, Pleij CW, Bosch L., 1985

Export

0 Marked Publications

Open Data PUB

Web of Science

View record in Web of Science®

Sources

PMID: 15294028
PubMed | Europe PMC

Search this title in

Google Scholar