Paper by Erik D. Demaine

Reference:

Erik D. Demaine, Timothy Gomez, Elise Grizzell, Markus Hecher, Jayson Lynch, Robert Schweller, Ahmed Shalaby, and Damien Woods, “Domain-Based Nucleic-Acid Minimum Free Energy: Algorithmic Hardness and Parameterized Bounds”, in Proceedings of the 30th International Conference on DNA Computing and Molecular Programming (DNA 2024), LIPIcs, volume 314, Baltimore, Maryland, September 16–20, 2024, 2:1–2:24.

BibTeX

@InProceedings{MFE_DNA2024,
  AUTHOR        = {Erik D. Demaine and Timothy Gomez and Elise Grizzell and Markus Hecher and Jayson Lynch and Robert Schweller and Ahmed Shalaby and Damien Woods},
  TITLE         = {Domain-Based Nucleic-Acid Minimum Free Energy: Algorithmic Hardness and Parameterized Bounds},
  BOOKTITLE     = {Proceedings of the 30th International Conference on DNA Computing and Molecular Programming (DNA 2024)},
  bookurl       = {https://www.dna30.org/},
  ADDRESS       = {Baltimore, Maryland},
  SERIES        = {LIPIcs},
  VOLUME        = 314,
  MONTH         = {September 16--20},
  YEAR          = 2024,
  PAGES         = {2:1--2:24},

  length        = {24 pages},
  withstudent   = 1,
  doi           = {https://dx.doi.org/10.4230/LIPIcs.DNA.30.2},
  dblp          = {https://dblp.org/rec/conf/dna/DemaineGGHLS0W24},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.4230/LIPIcs.DNA.30.2">LIPIcs</A>.},
}

Abstract:

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.

Comments:

This paper is also available from LIPIcs.

Length:

The paper is 24 pages.

Availability:

The paper is available in PDF (1002k).

See information on file formats.

[Google Scholar search]