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
• Complexity of pseudoknot prediction in simple models
• An efficient dynamic programming algorithm and implementation for RNA secondary structure prediction

Cited in

(2)

• RNA triplet repeats: improved algorithms for structure prediction and interactions
• An efficient algorithm to compute the minimum free energy of interacting nucleic acid strands

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)