2 Search Results for "Haley, David"

Document
DOI: 10.4230/LIPIcs.DNA.27.2
Computing Properties of Thermodynamic Binding Networks: An Integer Programming Approach

Authors: David Haley and David Doty

Published in: LIPIcs, Volume 205, 27th International Conference on DNA Computing and Molecular Programming (DNA 27) (2021)

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.
Cite as

David Haley and David Doty. Computing Properties of Thermodynamic Binding Networks: An Integer Programming Approach. In 27th International Conference on DNA Computing and Molecular Programming (DNA 27). Leibniz International Proceedings in Informatics (LIPIcs), Volume 205, pp. 2:1-2:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.27.2},
  URN =		{urn:nbn:de:0030-drops-146694},
  doi =		{10.4230/LIPIcs.DNA.27.2},
  annote =	{Keywords: thermodynamic binding networks, integer programming, constraint programming}
}
Document
DOI: 10.4230/LIPIcs.DNA.2020.3
Composable Computation in Leaderless, Discrete Chemical Reaction Networks

Authors: Hooman Hashemi, Ben Chugg, and Anne Condon

Published in: LIPIcs, Volume 174, 26th International Conference on DNA Computing and Molecular Programming (DNA 26) (2020)

Abstract
We classify the functions f:ℕ^d → ℕ that are stably computable by leaderless, output-oblivious discrete (stochastic) Chemical Reaction Networks (CRNs). CRNs that compute such functions are systems of reactions over species that include d designated input species, whose initial counts represent an input x ∈ ℕ^d, and one output species whose eventual count represents f(x). Chen et al. showed that the class of functions computable by CRNs is precisely the semilinear functions. In output-oblivious CRNs, the output species is never a reactant. Output-oblivious CRNs are easily composable since a downstream CRN can consume the output of an upstream CRN without affecting its correctness. Severson et al. showed that output-oblivious CRNs compute exactly the subclass of semilinear functions that are eventually the minimum of quilt-affine functions, i.e., affine functions with different intercepts in each of finitely many congruence classes. They call such functions the output-oblivious functions. A leaderless CRN can compute only superadditive functions, and so a leaderless output-oblivious CRN can compute only superadditive, output-oblivious functions. In this work we show that a function f:ℕ^d → ℕ is stably computable by a leaderless, output-oblivious CRN if and only if it is superadditive and output-oblivious.
Cite as

Hooman Hashemi, Ben Chugg, and Anne Condon. Composable Computation in Leaderless, Discrete Chemical Reaction Networks. In 26th International Conference on DNA Computing and Molecular Programming (DNA 26). Leibniz International Proceedings in Informatics (LIPIcs), Volume 174, pp. 3:1-3:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{hashemi_et_al:LIPIcs.DNA.2020.3,
  author =	{Hashemi, Hooman and Chugg, Ben and Condon, Anne},
  title =	{{Composable Computation in Leaderless, Discrete Chemical Reaction Networks}},
  booktitle =	{26th International Conference on DNA Computing and Molecular Programming (DNA 26)},
  pages =	{3:1--3:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-163-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{174},
  editor =	{Geary, Cody and Patitz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.2020.3},
  URN =		{urn:nbn:de:0030-drops-129560},
  doi =		{10.4230/LIPIcs.DNA.2020.3},
  annote =	{Keywords: Chemical Reaction Networks, Stable Function Computation, Output-Oblivious, Output-Monotonic}
}
  • Refine by Author
  • 1 Chugg, Ben
  • 1 Condon, Anne
  • 1 Doty, David
  • 1 Haley, David
  • 1 Hashemi, Hooman

  • Refine by Classification
  • 1 Theory of computation → Formal languages and automata theory
  • 1 Theory of computation → Models of computation
  • 1 Theory of computation → Theory and algorithms for application domains

  • Refine by Keyword
  • 1 Chemical Reaction Networks
  • 1 Output-Monotonic
  • 1 Output-Oblivious
  • 1 Stable Function Computation
  • 1 constraint programming
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2020
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact