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

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

Zeitschriftenaufsatz | Veröffentlicht | Englisch
Reeder, Jens; Giegerich, RobertUniBi
Abstract / Bemerkung
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.
BMC Bioinformatics
Page URI


Reeder J, Giegerich R. Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics. BMC Bioinformatics. 2004;5(1): 104.
Reeder, J., & Giegerich, R. (2004). Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics. BMC Bioinformatics, 5(1), 104.
Reeder, Jens, and Giegerich, Robert. 2004. “Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics”. BMC Bioinformatics 5 (1): 104.
Reeder, J., and Giegerich, R. (2004). Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics. BMC Bioinformatics 5:104.
Reeder, J., & Giegerich, R., 2004. Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics. BMC Bioinformatics, 5(1): 104.
J. Reeder and R. Giegerich, “Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics”, BMC Bioinformatics, vol. 5, 2004, : 104.
Reeder, J., Giegerich, R.: Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics. BMC Bioinformatics. 5, : 104 (2004).
Reeder, Jens, and Giegerich, Robert. “Design, implementation and evaluation of a practical pseudoknot folding algorithm based on thermodynamics”. BMC Bioinformatics 5.1 (2004): 104.
Alle Dateien verfügbar unter der/den folgenden Lizenz(en):
Copyright Statement:
Dieses Objekt ist durch das Urheberrecht und/oder verwandte Schutzrechte geschützt. [...]
Access Level
OA Open Access
Zuletzt Hochgeladen
MD5 Prüfsumme

103 Zitationen in Europe PMC

Daten bereitgestellt von Europe PubMed Central.

An algebraic language for RNA pseudoknots comparison.
Quadrini M, Tesei L, Merelli E., BMC Bioinformatics 20(suppl 4), 2019
PMID: 30999864
Bi-objective integer programming for RNA secondary structure prediction with pseudoknots.
Legendre A, Angel E, Tahi F., BMC Bioinformatics 19(1), 2018
PMID: 29334887
Structure-Function Model for Kissing Loop Interactions That Initiate Dimerization of Ty1 RNA.
Gamache ER, Doh JH, Ritz J, Laederach A, Bellaousov S, Mathews DH, Curcio MJ., Viruses 9(5), 2017
PMID: 28445416
RNA folding with hard and soft constraints.
Lorenz R, Hofacker IL, Stadler PF., Algorithms Mol Biol 11(), 2016
PMID: 27110276
The RNA shapes studio.
Janssen S, Giegerich R., Bioinformatics 31(3), 2015
PMID: 25273103
Thermodynamic matchers for the construction of the cuckoo RNA family.
Reinkensmeier J, Giegerich R., RNA Biol 12(2), 2015
PMID: 25779873
Kinetic partitioning mechanism of HDV ribozyme folding.
Chen J, Gong S, Wang Y, Zhang W., J Chem Phys 140(2), 2014
PMID: 24437918
Molecular characterization and phylogenetic analysis of the genome of porcine torovirus.
Sun H, Lan D, Lu L, Chen M, Wang C, Hua X., Arch Virol 159(4), 2014
PMID: 24122107
Structure and activity of AbiQ, a lactococcal endoribonuclease belonging to the type III toxin-antitoxin system.
Samson JE, Spinelli S, Cambillau C, Moineau S., Mol Microbiol 87(4), 2013
PMID: 23279123
Positional mapping and candidate gene analysis of the mouse Ccs3 locus that regulates differential susceptibility to carcinogen-induced colorectal cancer.
Meunier C, Van Der Kraak L, Turbide C, Groulx N, Labouba I, Cingolani P, Blanchette M, Yeretssian G, Mes-Masson AM, Saleh M, Beauchemin N, Gros P., PLoS One 8(3), 2013
PMID: 23516545
Genetic variations of the A13/A14 repeat located within the EGFR 3' untranslated region have no oncogenic effect in patients with colorectal cancer.
Sarafan-Vasseur N, Sefrioui D, Tougeron D, Lamy A, Blanchard F, Le Pessot F, Di Fiore F, Michel P, Bézieau S, Latouche JB, Frebourg T, Sesboüé R., BMC Cancer 13(), 2013
PMID: 23565769
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
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
Sequence-structure relationships in yeast mRNAs.
Chursov A, Walter MC, Schmidt T, Mironov A, Shneider A, Frishman D., Nucleic Acids Res 40(3), 2012
PMID: 21954438
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
Identifying complete RNA structural ensembles including pseudoknots.
Gupta A, Rahman R, Li K, Gribskov M., RNA Biol 9(2), 2012
PMID: 22418849
Mechanistic Roles of Noncoding RNAs in Lung Cancer Biology and Their Clinical Implications.
Enfield KS, Pikor LA, Martinez VD, Lam WL., Genet Res Int 2012(), 2012
PMID: 22852089
Computational analysis of noncoding RNAs.
Washietl S, Will S, Hendrix DA, Goff LA, Rinn JL, Berger B, Kellis M., Wiley Interdiscip Rev RNA 3(6), 2012
PMID: 22991327
On the combinatorics of sparsification.
Huang FW, Reidys CM., Algorithms Mol Biol 7(1), 2012
PMID: 23088372
Heuristic RNA pseudoknot prediction including intramolecular kissing hairpins.
Sperschneider J, Datta A, Wise MJ., RNA 17(1), 2011
PMID: 21098139
Topology and prediction of RNA pseudoknots.
Reidys CM, Huang FW, Andersen JE, Penner RC, Stadler PF, Nebel ME., Bioinformatics 27(8), 2011
PMID: 21335320
TT2NE: a novel algorithm to predict RNA secondary structures with pseudoknots.
Bon M, Orland H., Nucleic Acids Res 39(14), 2011
PMID: 21593129
Comparative complete genome analysis of Indian type A foot-and-mouth disease virus field isolates.
Subramaniam S, Sanyal A, Mohapatra JK, Hemadri D, Pattnaik B., Virus Genes 43(2), 2011
PMID: 21604149
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
Understanding the transcriptome through RNA structure.
Wan Y, Kertesz M, Spitale RC, Segal E, Chang HY., Nat Rev Genet 12(9), 2011
PMID: 21850044
Finding cancer-associated miRNAs: methods and tools.
Oulas A, Karathanasis N, Louloupi A, Poirazi P., Mol Biotechnol 49(1), 2011
PMID: 21607762
RNA pseudoknots: folding and finding.
Liu B, Mathews DH, Turner DH., F1000 Biol Rep 2(), 2010
PMID: 20495679
DotKnot: pseudoknot prediction using the probability dot plot under a refined energy model.
Sperschneider J, Datta A., Nucleic Acids Res 38(7), 2010
PMID: 20123730
A 3' terminal stem-loop structure in Nodamura virus RNA2 forms an essential cis-acting signal for RNA replication.
Rosskopf JJ, Upton JH, Rodarte L, Romero TA, Leung MY, Taufer M, Johnson KL., Virus Res 150(1-2), 2010
PMID: 20176063
Lifting prediction to alignment of RNA pseudoknots.
Möhl M, Will S, Backofen R., J Comput Biol 17(3), 2010
PMID: 20377455
RNA secondary structure prediction using a self-consistent mean field approach.
Kleesiek J, Torda AE., J Comput Chem 31(6), 2010
PMID: 19899145
Approximation algorithms for predicting RNA secondary structures with arbitrary pseudoknots.
Jiang M., IEEE/ACM Trans Comput Biol Bioinform 7(2), 2010
PMID: 20431151
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
Thermodynamics of RNA structures by Wang-Landau sampling.
Lou F, Clote P., Bioinformatics 26(12), 2010
PMID: 20529917
K-partite RNA secondary structures.
Jiang M, Tejada PJ, Lasisi RO, Cheng S, Fechser DS., J Comput Biol 17(7), 2010
PMID: 20632871
Sparsification of RNA structure prediction including pseudoknots.
Möhl M, Salari R, Will S, Backofen R, Sahinalp SC., Algorithms Mol Biol 5(), 2010
PMID: 21194463
PseudoBase++: an extension of PseudoBase for easy searching, formatting and visualization of pseudoknots.
Taufer M, Licon A, Araiza R, Mireles D, van Batenburg FH, Gultyaev AP, Leung MY., Nucleic Acids Res 37(database issue), 2009
PMID: 18988624
MicroRNAs and cancer-the search begins!
Oulas A, Reczko M, Poirazi P., IEEE Trans Inf Technol Biomed 13(1), 2009
PMID: 19129025
Prediction of RNA secondary structure with pseudoknots using integer programming.
Poolsap U, Kato Y, Akutsu T., BMC Bioinformatics 10 Suppl 1(), 2009
PMID: 19208139
Functional genomic analysis of two Staphylococcus aureus phages isolated from the dairy environment.
García P, Martínez B, Obeso JM, Lavigne R, Lurz R, Rodríguez A., Appl Environ Microbiol 75(24), 2009
PMID: 19837832
Folding 3-noncrossing RNA pseudoknot structures.
Huang FW, Peng WW, Reidys CM., J Comput Biol 16(11), 2009
PMID: 19958083
RNA folding on the 3D triangular lattice.
Gillespie J, Mayne M, Jiang M., BMC Bioinformatics 10(), 2009
PMID: 19891777
Predicting RNA secondary structures with pseudoknots by MCMC sampling.
Metzler D, Nebel ME., J Math Biol 56(1-2), 2008
PMID: 17589847
Complete nucleotide sequence and experimental host range of Okra mosaic virus.
Stephan D, Siddiqua M, Ta Hoang A, Engelmann J, Winter S, Maiss E., Virus Genes 36(1), 2008
PMID: 18049886
Introduction to special issue on RNA.
Clote P., J Math Biol 56(1-2), 2008
PMID: 17938928
KnotSeeker: heuristic pseudoknot detection in long RNA sequences.
Sperschneider J, Datta A., RNA 14(4), 2008
PMID: 18314500
Shape based indexing for faster search of RNA family databases.
Janssen S, Reeder J, Giegerich R., BMC Bioinformatics 9(), 2008
PMID: 18312625
Topological classification of RNA structures.
Bon M, Vernizzi G, Orland H, Zee A., J Mol Biol 379(4), 2008
PMID: 18485361
FlexStem: improving predictions of RNA secondary structures with pseudoknots by reducing the search space.
Chen X, He SM, Bu D, Zhang F, Wang Z, Chen R, Gao W., Bioinformatics 24(18), 2008
PMID: 18586700
The genome and proteome of the Kluyvera bacteriophage Kvp1--another member of the T7-like Autographivirinae.
Lingohr EJ, Villegas A, She YM, Ceyssens PJ, Kropinski AM., Virol J 5(), 2008
PMID: 18937848
High sensitivity RNA pseudoknot prediction.
Huang X, Ali H., Nucleic Acids Res 35(2), 2007
PMID: 17179177
Bridging the gap in RNA structure prediction.
Shapiro BA, Yingling YG, Kasprzak W, Bindewald E., Curr Opin Struct Biol 17(2), 2007
PMID: 17383172
Correlation between mechanical strength of messenger RNA pseudoknots and ribosomal frameshifting.
Hansen TM, Reihani SN, Oddershede LB, Sørensen MA., Proc Natl Acad Sci U S A 104(14), 2007
PMID: 17389398
pknotsRG: RNA pseudoknot folding including near-optimal structures and sliding windows.
Reeder J, Steffen P, Giegerich R., Nucleic Acids Res 35(web server issue), 2007
PMID: 17478505
FSDB: a frameshift signal database.
Moon S, Byun Y, Han K., Comput Biol Chem 31(4), 2007
PMID: 17631420
RNA structure: bioinformatic analysis.
Jossinet F, Ludwig TE, Westhof E., Curr Opin Microbiol 10(3), 2007
PMID: 17548241
RNA Movies 2: sequential animation of RNA secondary structures.
Kaiser A, Krüger J, Evers DJ., Nucleic Acids Res 35(web server issue), 2007
PMID: 17567618
Locomotif: from graphical motif description to RNA motif search.
Reeder J, Reeder J, Giegerich R., Bioinformatics 23(13), 2007
PMID: 17646322
Viral RNA pseudoknots: versatile motifs in gene expression and replication.
Brierley I, Pennell S, Gilbert RJ., Nat Rev Microbiol 5(8), 2007
PMID: 17632571
A method for finding optimal rna secondary structures using a new entropy model (vsfold).
Dawson W, Fujiwara K, Kawai G, Futamura Y, Yamamoto K., Nucleosides Nucleotides Nucleic Acids 25(2), 2006
PMID: 16541960
Beyond Mfold: recent advances in RNA bioinformatics.
Reeder J, Höchsmann M, Rehmsmeier M, Voss B, Giegerich R., J Biotechnol 124(1), 2006
PMID: 16530285
Partition function and base pairing probabilities of RNA heterodimers.
Bernhart SH, Tafer H, Mückstein U, Flamm C, Stadler PF, Hofacker IL., Algorithms Mol Biol 1(1), 2006
PMID: 16722605
Prediction of RNA secondary structure by free energy minimization.
Mathews DH, Turner DH., Curr Opin Struct Biol 16(3), 2006
PMID: 16713706
Prediction of structured non-coding RNAs in the genomes of the nematodes Caenorhabditis elegans and Caenorhabditis briggsae.
Missal K, Zhu X, Rose D, Deng W, Skogerbø G, Chen R, Stadler PF., J Exp Zool B Mol Dev Evol 306(4), 2006
PMID: 16425273
Structural analysis of aligned RNAs.
Voss B., Nucleic Acids Res 34(19), 2006
PMID: 17020924
XML schemas for common bioinformatic data types and their application in workflow systems.
Seibel PN, Krüger J, Hartmeier S, Schwarzer K, Löwenthal K, Mersch H, Dandekar T, Giegerich R., BMC Bioinformatics 7(), 2006
PMID: 17087823
A heuristic approach for detecting RNA H-type pseudoknots.
Huang CH, Lu CL, Chiu HT., Bioinformatics 21(17), 2005
PMID: 15994188
Versatile and declarative dynamic programming using pair algebras.
Steffen P, Giegerich R., BMC Bioinformatics 6(), 2005
PMID: 16156887
HotKnots: heuristic prediction of RNA secondary structures including pseudoknots.
Ren J, Rastegari B, Condon A, Hoos HH., RNA 11(10), 2005
PMID: 16199760
Prediction of consensus RNA secondary structures including pseudoknots.
Witwer C, Hofacker IL, Stadler PF., IEEE/ACM Trans Comput Biol Bioinform 1(2), 2004
PMID: 17048382
A comprehensive comparison of comparative RNA structure prediction approaches.
Gardner PP, Giegerich R., BMC Bioinformatics 5(), 2004
PMID: 15458580

36 References

Daten bereitgestellt von Europe PubMed Central.

Pseudoknots in prion protein mRNAs confirmed by comparative sequence analysis and pattern searching.
Barrette I, Poisson G, Gendron P, Major F., Nucleic Acids Res. 29(3), 2001
PMID: 11160898
The brave new world of RNA.
Dennis C., Nature 418(6894), 2002
PMID: 12110860
RNA secondary structures and their prediction
Zuker M, Sankoff S., 1984
Fast folding and comparison of RNA secondary structures
Hofacker I, Fontana W, Stadler P, Bonhoeffer L, Tacker M, Schuster P., 1994
Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure.
Mathews DH, Sabina J, Zuker M, Turner DH., J. Mol. Biol. 288(5), 1999
PMID: 10329189
Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots
Akutsu T., 2000
RNA pseudoknot prediction in energy-based models.
Lyngso RB, Pedersen CN., J. Comput. Biol. 7(3-4), 2000
PMID: 11108471
An RNA folding method capable of identifying pseudoknots and base triples.
Tabaska JE, Cary RB, Gabow HN, Stormo GD., Bioinformatics 14(8), 1998
PMID: 9789095
Pseudoknots in RNA secondary structures
Lyngsø RB, Pedersen CN., 2000
RNA secondary structure prediction with simple pseudoknots
Deogun J, Donis E, Komina O, Ma F., 2004
PseudoBase homepage
Algebraic Dynamic Programming
Giegerich R, Meyer C., 2002
Explaining and controlling ambiguity in dynamic programming
Giegerich R., 2000
Complete suboptimal folding of RNA and the stability of secondary structures.
Wuchty S, Fontana W, Hofacker IL, Schuster P., Biopolymers 49(2), 1999
PMID: 10070264
How RNA folds.
Tinoco I Jr, Bustamante C., J. Mol. Biol. 293(2), 1999
PMID: 10550208
The language of RNA: a formal grammar that includes pseudoknots.
Rivas E, Eddy SR., Bioinformatics 16(4), 2000
PMID: 10869031
Stochastic modeling of RNA pseudoknotted structures: a grammatical approach.
Cai L, Malmberg RL, Wu Y., Bioinformatics 19 Suppl 1(), 2003
PMID: 12855439
A discipline of dynamic programming over sequence data
Giegerich R, Meyer C, Steffen P., 2004
RNAMotif, an RNA secondary structure definition and search algorithm.
Macke TJ, Ecker DJ, Gutell RR, Gautheret D, Case DA, Sampath R., Nucleic Acids Res. 29(22), 2001
PMID: 11713323
A systematic approach to dynamic programming in bioinformatics.
Giegerich R., Bioinformatics 16(8), 2000
PMID: 11099253
RNA folding via algebraic dynamic programming
Evers D., 2003
Algebraic Dynamic Programming home page
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
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

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®

PMID: 15294028
PubMed | Europe PMC

Suchen in

Google Scholar