Predicting minimum free energy structures of multi-stranded nucleic acid complexes is APX-hard

DOI10.4230/LIPICS.DNA.27.9MaRDI QIDQ6076676FDOQ6076676

Authors: Anne Condon, Monir Hajiaghayi, Chris Thachuk 

Publication date: 21 September 2023

Recommendations

• NP-completeness of the energy barrier problem without pseudoknots and temporary arcs
• NP-Completeness of the Direct Energy Barrier Problem without Pseudoknots
• Thermodynamic Analysis of Interacting Nucleic Acid Strands
• Automata, Languages and Programming
• Computational Science – ICCS 2005

zbMATH Keywords

APX-hardnessNP-hardnessnucleic acid secondary structure prediction

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Biologically inspired models of computation (DNA computing, membrane computing, etc.) (68Q07)

This page was built for publication: Predicting minimum free energy structures of multi-stranded nucleic acid complexes is APX-hard

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