License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DNA.27.9
URN: urn:nbn:de:0030-drops-146765
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14676/
Go to the corresponding LIPIcs Volume Portal

Condon, Anne ; Hajiaghayi, Monir ; Thachuk, Chris

Predicting Minimum Free Energy Structures of Multi-Stranded Nucleic Acid Complexes Is APX-Hard

pdf-format:
LIPIcs-DNA-27-9.pdf (1 MB)

Abstract

Given multiple nucleic acid strands, what is the minimum free energy (MFE) secondary structure that they can form? As interacting nucleic acid strands are the basis for DNA computing and molecular programming, e.g., in DNA self-assembly and DNA strand displacement systems, determining the MFE structure is an important step in the design and verification of these systems. Efficient dynamic programming algorithms are well known for predicting the MFE pseudoknot-free secondary structure of a single nucleic acid strand. In contrast, we prove that for a simple energy model, the problem of predicting the MFE pseudoknot-free secondary structure formed from multiple interacting nucleic acid strands is NP-hard and also APX-hard. The latter result implies that there does not exist a polynomial time approximation scheme for this problem, unless ? = NP, and it suggests that heuristic methods should be investigated.

BibTeX - Entry

@InProceedings{condon_et_al:LIPIcs.DNA.27.9,
  author =	{Condon, Anne and Hajiaghayi, Monir and Thachuk, Chris},
  title =	{{Predicting Minimum Free Energy Structures of Multi-Stranded Nucleic Acid Complexes Is APX-Hard}},
  booktitle =	{27th International Conference on DNA Computing and Molecular Programming (DNA 27)},
  pages =	{9:1--9:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-205-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{205},
  editor =	{Lakin, Matthew R. and \v{S}ulc, Petr},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14676},
  URN =		{urn:nbn:de:0030-drops-146765},
  doi =		{10.4230/LIPIcs.DNA.27.9},
  annote =	{Keywords: Nucleic Acid Secondary Structure Prediction, APX-Hardness, NP-Hardness}
}

Keywords: Nucleic Acid Secondary Structure Prediction, APX-Hardness, NP-Hardness
Collection: 27th International Conference on DNA Computing and Molecular Programming (DNA 27)
Issue Date: 2021
Date of publication: 08.09.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI