Complexity of pseudoknot prediction in simple models

DOI10.1007/978-3-540-27836-8_77MaRDI QIDQ5466525zbMATH OpenOpenAlexFDO

Authors Rune B. Lyngsø

Publication date 24 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b99859

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Approximation algorithms (68W25) Protein sequences, DNA sequences (92D20)

Recommendations

• Dynamic programming algorithms for RNA secondary structure prediction with pseudoknots
• A new pseudoknots folding algorithm for RNA structure prediction
• Classifying RNA pseudoknotted structures
• Impact of the energy model on the complexity of RNA folding with pseudoknots
• Prediction for RNA planar pseudoknots

Cited in

(22)

• Computational prediction of nucleic acid secondary structure: Methods, applications, and challenges
• On recovering syntenic blocks from comparative maps
• Prediction for RNA planar pseudoknots
• Pseudoknot-generating operation
• Impact of the energy model on the complexity of RNA folding with pseudoknots
• Speedup of RNA pseudoknotted secondary structure recurrence computation with the four-Russians method
• A new method for prediction of RNA secondary structure with pseudoknots, based on helix removal and refinement
• NP-Completeness of the Direct Energy Barrier Problem without Pseudoknots
• Counting RNA pseudoknotted structures (extended abstract)
• scientific article; zbMATH DE number 7205101 (Why is no real title available?)
• Improved Approximation Algorithms for Predicting RNA Secondary Structures with Arbitrary Pseudoknots
• Prediction and statistics of pseudoknots in RNA structures using exactly clustered stochastic simulations
• On Recovering Syntenic Blocks from Comparative Maps
• Inapproximability of maximal strip recovery
• A new pseudoknots folding algorithm for RNA structure prediction
• Predicting minimum free energy structures of multi-stranded nucleic acid complexes is APX-hard
• New approximation algorithms for RNA secondary structures prediction problems by local search
• Automated design of dynamic programming schemes for RNA folding with pseudoknots
• On the page number of RNA secondary structures with pseudoknots
• Automated rendering of multi-stranded DNA complexes with pseudoknots
• On realizing shapes in the theory of RNA neutral networks
• Rapid ab initio prediction of RNA pseudoknots via graph tree decomposition

This page was built for publication: Complexity of pseudoknot prediction in simple models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5466525)