2026-07-24T08:20:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20930 2024-09-09T05:13:10Z ddc:004 open_access

Domain-Based Nucleic-Acid Minimum Free Energy: Algorithmic Hardness and Parameterized Bounds Demaine, Erik D. Gomez, Timothy Grizzell, Elise Hecher, Markus Lynch, Jayson Schweller, Robert Shalaby, Ahmed Woods, Damien Domain-based DNA designs minimum free energy efficient algorithms NP-hard P-hard NC fixed-parameter tractable Molecular programmers and nanostructure engineers use domain-level design to abstract away messy DNA/RNA sequence, chemical and geometric details. Such domain-level abstractions are enforced by sequence design principles and provide a key principle that allows scaling up of complex multistranded DNA/RNA programs and structures. Determining the most favoured secondary structure, or Minimum Free Energy (MFE), of a set of strands, is typically studied at the sequence level but has seen limited domain-level work. We analyse the computational complexity of MFE for multistranded systems in a simple setting were we allow only 1 or 2 domains per strand. On the one hand, with 2-domain strands, we find that the MFE decision problem is NP-complete, even without pseudoknots, and requires exponential time algorithms assuming SAT does. On the other hand, in the simplest case of 1-domain strands there are efficient MFE algorithms for various binding modes. However, even in this single-domain case, MFE is P-hard for promiscuous binding, where one domain may bind to multiple as experimentally used by Nikitin [Nat Chem., 2023], which in turn implies that strands consisting of a single domain efficiently implement arbitrary Boolean circuits. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Erik D. Demaine and Timothy Gomez and Elise Grizzell and Markus Hecher and Jayson Lynch and Robert Schweller and Ahmed Shalaby and Damien Woods 2024 Is Part Of LIPIcs, Volume 314, 30th International Conference on DNA Computing and Molecular Programming (DNA 30) (2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DNA.30.2 urn:nbn:de:0030-drops-209304 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.30.2 eng https://creativecommons.org/licenses/by/4.0/legalcode