Hardness of RNA folding problem with four symbols

DOI10.4230/LIPICS.CPM.2016.13MaRDI QIDQ5369547zbMATH OpenOpenAlexFDO

Authors Yi-Jun Chang

Publication date 17 October 2017

Full work available at URL https://doi.org/10.4230/LIPIcs.CPM.2016.13

zbMATH Keywords

cliqueconditional lower boundDyck edit distancelongest common subsequenceRNA folding

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32) Protein sequences, DNA sequences (92D20)

Recommendations

• Hardness of RNA folding problem with four symbols
• Impact of the energy model on the complexity of RNA folding with pseudoknots
• Extending the Hardness of RNA Secondary Structure Comparison
• Sparse RNA folding: time and space efficient algorithms
• Sparse RNA Folding: Time and Space Efficient Algorithms

Cited in

(9)

• Hardness of RNA folding problem with four symbols
• If the current clique algorithms are optimal, so is Valiant's parser
• Truly subcubic algorithms for language edit distance and RNA folding via fast bounded-difference min-plus product
• Towards hardness of approximation for polynomial time problems
• Even faster elastic-degenerate string matching via fast matrix multiplication
• Elastic-Degenerate String Matching via Fast Matrix Multiplication
• Faster combinatorial \(k\)-clique algorithms
• Faster combinatorial k-clique algorithms
• The role of regularity in (hyper-)clique detection and implications for optimizing Boolean CSPs

This page was built for publication: Hardness of RNA folding problem with four symbols

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