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

DOI10.4230/LIPICS.DNA.27.9MaRDI QIDQ6076676zbMATH OpenFDO

Authors Anne Condon, Monir Hajiaghayi, Chris Thachuk

Publication date 21 September 2023

Full work available at URL https://doi.org/10.4230/LIPICS.DNA.27.9

zbMATH Keywords

APX-hardnessNP-hardnessnucleic acid secondary structure prediction

Mathematics Subject Classification ID

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

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

Cited in

(1)

• RNA triplet repeats: improved algorithms for structure prediction and interactions

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)