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

BackgroundThe 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.ResultsWe 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.ConclusionsRNA pseudoknots of medium size can now be predicted reliably as well as efficiently by the new algorithm.

• Publication year

  2004

• Venue

  BMC Bioinformatics

• Publication date

  2004-08-04

• Fields of study

  Biology, Medicine, Computer Science

• Identifiers
  DOI 10.1186/1471-2105-5-104PMID 15294028PMCID 514697
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• An Iterated loop matching approach to the prediction of RNA secondary structures with pseudoknots

  2004cited by this paper
• A discipline of dynamic programming over sequence data

  2004cited by this paper
• RNA Secondary Structure Prediction with Simple Pseudoknots

  2004cited by this paper
• A partition function algorithm for nucleic acid secondary structure including pseudoknots

  2003cited by this paper
• RNA folding via algebraic dynamic programming

  2003cited by this paper
• RnaViz 2: an improved representation of RNA secondary structure

  2003cited by this paper
• Stochastic modeling of RNA pseudoknotted structures: a grammatical approach

  2003cited by this paper
• Algebraic Dynamic Programming

  2002influential reference
• Gene regulation: The brave new world of RNA

  2002cited by this paper
• RNAMotif, an RNA secondary structure definition and search algorithm.

  2001cited by this paper
• Pseudoknots in prion protein mRNAs confirmed by comparative sequence analysis and pattern searching.

  2001cited by this paper
• Reducing the Conformation Space in RNA Structure Prediction

  2001cited by this paper
• RNA Pseudoknot Prediction in Energy-Based Models

  2000influential reference
• Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots

  2000influential reference
• The language of RNA: a formal grammar that includes pseudoknots

  2000cited by this paper
• A systematic approach to dynamic programming in bioinformatics

  2000influential reference
• Pseudoknots in RNA secondary structures

  2000cited by this paper
• Explaining and Controlling Ambiguity in Dynamic Programming

  2000cited by this paper
• Expanded sequence dependence of thermodynamic parameters improves prediction of RNA secondary structure.

  1999cited by this paper
• How RNA folds.

  1999cited by this paper
• Complete suboptimal folding of RNA and the stability of secondary structures.

  1999cited by this paper
• An approximation of loop free energy values of RNA H-pseudoknots.

  1999cited by this paper
• An RNA folding method capable of identifying pseudoknots and base triples

  1998cited by this paper
• A dynamic programming algorithm for RNA structure prediction including pseudoknots.

  1998cited by this paper
• Crystal structure of a hepatitis delta virus ribozyme

  1998cited by this paper
• Linguistic approaches to biological sequences

  1997cited by this paper
• The role of the pseudoknot at the 3' end of turnip yellow mosaic virus RNA in minus-strand synthesis by the viral RNA-dependent RNA polymerase

  1997cited by this paper
• A Grammar-Based Unification of Several Alignment and Folding Algorithms

  1996cited by this paper
• Fast folding and comparison of RNA secondary structures

  1994influential reference
• RNA pseudoknots that inhibit human immunodeficiency virus type 1 reverse transcriptase.

  1992cited by this paper
• Conserved sequences and structures of group I introns: building an active site for RNA catalysis--a review.

  1988cited by this paper
• Five pseudoknots are present at the 204 nucleotides long 3' noncoding region of tobacco mosaic virus RNA.

  1985cited by this paper
• RNA secondary structures and their prediction

  1984cited by this paper

• Hierarchical analysis of RNA secondary structures with pseudoknots based on sections

  2025cites this paper
• Evaluating Performance of Different RNA Secondary Structure Prediction Programs Using Self-cleaving Ribozymes

  2024cites this paper
• Domain-Based Nucleic-Acid Minimum Free Energy: Algorithmic Hardness and Parameterized Bounds

  2024cites this paper
• CParty: hierarchically constrained partition function of RNA pseudoknots

  2024cites this paper
• The effect of the loop on the thermodynamic and kinetic of single base pair in pseudoknot.

  2024cites this paper
• Transformer-Based Refinement of Pseudoknot Predictions in RNA Secondary Structures

  2024cites this paper
• ML-Based RNA Secondary Structure Prediction Methods: A Survey

  2024cites this paper
• RnaBench: A Comprehensive Library for In Silico RNA Modelling

  2024cites this paper
• An efficient algorithm to compute the minimum free energy of interacting nucleic acid strands

  2024cites this paper
• DinoKnot: Duplex Interaction of Nucleic Acids With PseudoKnots

  2024cites this paper
• Pseudoknots in RNA Structure Prediction

  2023cites this paper
• Nucleic Acid Structure Prediction Including Pseudoknots Through Direct Enumeration of States: A User's Guide to the LandscapeFold Algorithm.

  2023cites this paper
• RNA Structure Prediction, Analysis, and Design: An Introduction to Web-Based Tools.

  2022cites this paper
• Length-Based Substructure Mutation Policies for Improved RNA Design in Simulated Annealing

  2022cites this paper
• Direct Inference of Base-Pairing Probabilities with Neural Networks Improves Prediction of RNA Secondary Structures with Pseudoknots

  2022cites this paper
• Knotify: An Efficient Parallel Platform for RNA Pseudoknot Prediction Using Syntactic Pattern Recognition

  2022cites this paper
• RNA secondary structure factorization in prime tangles

  2022cites this paper
• Accurate prediction of RNA secondary structure including pseudoknots through solving minimum-cost flow with learned potentials

  2022cites this paper
• RNA Structure Prediction

  2021cites this paper
• Prediction of RNA secondary structure including pseudoknots for long sequences

  2021cites this paper
• Sequence Analysis

  2020cites this paper
• Ensemble Algorithms and Analytic Combinatorics in RNA Bioinformatics and Beyond. (Algorithmes ensemblistes et combinatoire analytique en Bioinformatique des ARN)

  2020cites this paper
• Advancements in RNA Secondary Structure Prediction using Machine Learning Methods

  2020cites this paper
• ATTfold: RNA Secondary Structure Prediction With Pseudoknots Based on Attention Mechanism

  2020cites this paper
• Dynamic Programming Applications: A Suvrvey

  2020cites this paper
• The molecular structure of long non-coding RNAs: emerging patterns and functional implications

  2020cites this paper
• In silico prediction of COVID-19 test efficiency with DinoKnot

  2020cites this paper
• Review of machine learning methods for RNA secondary structure prediction

  2020cites this paper
• RNA Secondary Structure Prediction using Machine Learning: A Review

  2020cites this paper
• Cotranscriptional Kinetic Folding of RNA Secondary Structures Including Pseudoknots

  2020cites this paper
• Analyzing genomic data using tensor-based orthogonal polynomials with application to synthetic RNAs

  2020cites this paper
• Nature inspired optimization algorithm for prediction of “minimum free energy” “RNA secondary structure”

  2019cites this paper
• LinearFold: linear-time approximate RNA folding by 5'-to-3' dynamic programming and beam search

  2019cites this paper
• An algebraic language for RNA pseudoknots comparison

  2019cites this paper
• A Polymer Physics Framework for the Entropy of Arbitrary Pseudoknots.

  2019cites this paper
• Research on RNA Secondary Structure Prediction Based on Decision Tree

  2019cites this paper
• The Predicting Algorithm of Barrier Tree in RNA Folding Structure

  2019cites this paper
• ThreshKnot: Thresholded ProbKnot for Improved RNA Secondary Structure Prediction

  2019cites this paper
• RNAknot: A new algorithm for RNA secondary structure prediction based on genetic algorithm and GRASP method

  2019cites this paper
• An efficient simulated annealing algorithm for the RNA secondary structure prediction with Pseudoknots

  2019cites this paper
• RNA secondary structure prediction using an ensemble of two-dimensional deep neural networks and transfer learning

  2019cites this paper
• Bi-objective integer programming for RNA secondary structure prediction with pseudoknots

  2018cites this paper
• RNA secondary structure prediction with pseudoknots: Contribution of algorithm versus energy model

  2018cites this paper
• A Novel Efficient Simulated Annealing Algorithm for the RNA Secondary Structure Predicting with Pseudoknots

  2018cites this paper
• Predicting Model and Algorithm in RNA Folding Structure Including Pseudoknots

  2018cites this paper
• Direct inference of base-pairing probabilities with neural networks improves RNA secondary structure prediction with pseudoknots

  2018influential citation
• Chapter 2 Computational Identification of miRNAs Involved in Cancer

  2018cites this paper
• A Multiobjective RNA Secondary Structure Prediction Algorithm Based on NSGAII

  2018cites this paper
• Knotty: efficient and accurate prediction of complex RNA pseudoknot structures

  2018cites this paper
• RNA structure prediction including pseudoknots through direct enumeration of states

  2018cites this paper
• In Silico Prediction of RNA Secondary Structure.

  2017cites this paper
• Structure-Function Model for Kissing Loop Interactions That Initiate Dimerization of Ty1 RNA

  2017cites this paper
• Fatgraph models of RNA structure

  2017cites this paper
• The Algorithm and Scheme of Prediction in RNA Folding Structure with Pseudoknots

  2017cites this paper
• RNA Secondary Structure an Overview

  2017cites this paper
• Sparsification Enables Predicting Kissing Hairpin Pseudoknot Structures of Long RNAs in Practice

  2017cites this paper
• A heuristic algorithm for RNA secondary structure based on genetic algorithm

  2017cites this paper
• Melting temperature highlights functionally important RNA structure and sequence elements in yeast mRNA coding regions

  2017cites this paper
• Comparative and integrative analysis of RNA structural profiling data: current practices and emerging questions

  2017cites this paper
• Practical structure-sequence alignment of pseudoknotted RNAs

  2017cites this paper
• Assessing Accuracies And Improving Efficiency For Segmentation-Based Rna Secondary Structure Prediction Methods

  2016cites this paper
• RNA folding with hard and soft constraints

  2016cites this paper
• The PTAS of Prediction for RNA Pseudoknotted Structure

  2016cites this paper
• Secondary Structure Prediction of Single Sequences Using RNAstructure.

  2016cites this paper
• BioCloud : A Network Cloud-Computing Method for Predicting RNA Secondary Structure

  2016cites this paper
• MMKnots : A max-margin model for RNA secondary structure prediction including pseudoknots

  2016cites this paper
• Genetic improvement of GPU software

  2016cites this paper
• Grow and Graft a Better CUDA pknotsRG for RNA Pseudoknot Free Energy Calculation

  2015influential citation
• Predicting Algorithm of RNA Folding Structure with Pseudoknots

  2015cites this paper
• Algorithms for prediction of RNA pseudoknotted secondary structures

  2015influential citation
• Prediction of Pre-microRNA Secondary Structure Based on Reverse Complementary Folding

  2015cites this paper
• Thermodynamic matchers for the construction of the cuckoo RNA family

  2015cites this paper
• Targeting and Specificity of RNA-binding Proteins

  2015cites this paper
• Classification of RNA Pseudoknots and Comparison of Structure Prediction Methods. (Classification de Pseudo-nœuds d'ARN et Comparaison de Méthodes de Prédiction de Structure)

  2015influential citation
• A new entropy model for RNA: part IV, The Minimum Free Energy (mFE) and the thermodynamically most-probable folding pathway (TMPFP)

  2015cites this paper
• Multi-objective optimization for RNA design with multiple target secondary structures

  2015cites this paper
• A permutation based simulated annealing algorithm to predict pseudoknotted RNA secondary structures

  2015cites this paper
• Une signature du polymorphisme structural d’acides ribonucléiques non-codants permettant de comparer leurs niveaux d’activités biochimiques

  2015cites this paper
• A New Parameterized Algorithm for Predicting the Secondary Structure of RNA Sequences Including Pseudoknots

  2015cites this paper
• Prediction Nucleic Acid Secondary Structure with Planar Pseudoknots and Genetic Algorithm

  2014cites this paper
• A fast and robust iterative algorithm for prediction of RNA pseudoknotted secondary

  2014cites this paper
• Kinetic partitioning mechanism of HDV ribozyme folding.

  2014cites this paper
• Dynamic matching algorithm for viral structure prediction.

  2014cites this paper
• A fast and robust iterative algorithm for prediction of RNA pseudoknotted secondary structures

  2014cites this paper
• Different RNA Secondary Structure Prediction Methods

  2014cites this paper
• Kisses, ambivalent models and more: Contributions to the analysis of RNA secondary structure

  2014cites this paper
• Additional Bioinformatic Analyses Involving Nucleic-Acid Sequences

  2014cites this paper
• Stochastic Models of –1 Programmed Ribosomal Frameshifting

  2014cites this paper
• Fine-grained parallelism accelerating for RNA secondary structure prediction with pseudoknots based on FPGA

  2014cites this paper
• Energy Parameters and Novel Algorithms for an Extended Nearest Neighbor Energy Model of RNA

  2014cites this paper
• Heuristic Algorithm for the Ribonucleic Acid Pseudoknotted Structure Prediction

  2014cites this paper
• Yield grammar analysis and product optimization in a domain-specific language for dynamic programming

  2014cites this paper
• Characteristics and Prediction of RNA Structure

  2014cites this paper
• The 3′ Untranslated Region of Pea Enation Mosaic Virus Contains Two T-Shaped, Ribosome-Binding, Cap-Independent Translation Enhancers

  2014cites this paper
• The RNA shapes studio

  2014influential citation
• Fine-Grained Parallel Application Specific Computing for RNA secondary Structure Prediction on FPGA

  2014cites this paper
• PreRkTAG: Prediction of RNA Knotted Structures Using Tree Adjoining Grammars

  2013cites this paper
• Computational prediction of RNA secondary structure.

  2013cites this paper
• Expression and translation of the COX-1b gene in human cells – no evidence of generation of COX-1b protein

  2013cites this paper
• GAknot: RNA secondary structures prediction with pseudoknots using genetic algorithm

  2013cites this paper