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.2
URN: urn:nbn:de:0030-drops-146694
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14669/
Go to the corresponding LIPIcs Volume Portal

Haley, David ; Doty, David

Computing Properties of Thermodynamic Binding Networks: An Integer Programming Approach

pdf-format:
LIPIcs-DNA-27-2.pdf (0.9 MB)

Abstract

The thermodynamic binding networks (TBN) model [Breik et al., 2021] is a tool for studying engineered molecular systems. The TBN model allows one to reason about their behavior through a simplified abstraction that ignores details about molecular composition, focusing on two key determinants of a system’s energetics common to any chemical substrate: how many molecular bonds are formed, and how many separate complexes exist in the system. We formulate as an integer program the NP-hard problem of computing stable (a.k.a., minimum energy) configurations of a TBN: those configurations that maximize the number of bonds and complexes. We provide open-source software solving this integer program. We give empirical evidence that this approach enables dramatically faster computation of TBN stable configurations than previous approaches based on SAT solvers [Breik et al., 2019]. Furthermore, unlike SAT-based approaches, our integer programming formulation can reason about TBNs in which some molecules have unbounded counts. These improvements in turn allow us to efficiently automate verification of desired properties of practical TBNs. Finally, we show that the TBN has a natural representation with a unique Hilbert basis describing the "fundamental components" out of which locally minimal energy configurations are composed. This characterization helps verify correctness of not only stable configurations, but entire "kinetic pathways" in a TBN.

BibTeX - Entry

@InProceedings{haley_et_al:LIPIcs.DNA.27.2,
  author =	{Haley, David and Doty, David},
  title =	{{Computing Properties of Thermodynamic Binding Networks: An Integer Programming Approach}},
  booktitle =	{27th International Conference on DNA Computing and Molecular Programming (DNA 27)},
  pages =	{2:1--2:16},
  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/14669},
  URN =		{urn:nbn:de:0030-drops-146694},
  doi =		{10.4230/LIPIcs.DNA.27.2},
  annote =	{Keywords: thermodynamic binding networks, integer programming, constraint programming}
}

Keywords: thermodynamic binding networks, integer programming, constraint programming
Collection: 27th International Conference on DNA Computing and Molecular Programming (DNA 27)
Issue Date: 2021
Date of publication: 08.09.2021
Supplementary Material: Software (Source Code): https://github.com/drhaley/stable_tbn

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