Creative Commons Attribution 4.0 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: https://drops.dagstuhl.de/opus/volltexte/2021/14676/
Condon, Anne ; Hajiaghayi, Monir ; Thachuk, Chris
Predicting Minimum Free Energy Structures of Multi-Stranded Nucleic Acid Complexes Is APX-Hard
| pdf-format: |
|
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 | |
| Seminar: | 27th International Conference on DNA Computing and Molecular Programming (DNA 27) | |
| Issue date: | 2021 | |
| Date of publication: | 08.09.2021 |
