Hardness of RNA folding problem with four symbols

DOI10.1016/j.tcs.2018.07.010zbMath1405.92211arXiv1511.04731OpenAlexW2885344880WikidataQ129440084 ScholiaQ129440084MaRDI QIDQ1711829

Yi-Jun Chang

Publication date: 18 January 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1511.04731

zbMATH Keywords

longest common subsequenceRNA foldingconditional lower boundDyck edit distance

Mathematics Subject Classification ID

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

Related Items (1)

The Fine-Grained Complexity of Median and Center String Problems Under Edit Distance

Cites Work

• Unnamed Item
• On the complexity of fixed parameter clique and dominating set
• Efficient algorithms for clique problems
• Approximation and exact algorithms for RNA secondary structure prediction and recognition of stochastic context-free languages
• Fast parallel and serial multidimensional approximate array matching
• Clustered Integer 3SUM via Additive Combinatorics
• Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
• Edit Distance with Duplications and Contractions Revisited
• Speedup of RNA Pseudoknotted Secondary Structure Recurrence Computation with the Four-Russians Method
• Biological Sequence Analysis
• On Hardness of Jumbled Indexing
• Faster all-pairs shortest paths via circuit complexity
• Hardness of RNA Folding Problem With Four Symbols.
• Fast approximation algorithms for the diameter and radius of sparse graphs

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