Search Results

Documents authored by Soloveichik, David

Document
DOI: 10.4230/LIPIcs.DNA.32.8
Amplification at Equilibrium: Structural and Thermodynamic Limitations, and Implementation

Authors: Hamidreza Akef, Chia-Yu Sung, Aneesh Vanguri, and David Soloveichik

Published in: LIPIcs, Volume 387, 32nd International Conference on DNA Computing and Molecular Programming (DNA 32) (2026)

Abstract
Amplifying weak molecular signals is essential in both natural and engineered biochemical systems. While most amplification schemes operate out of equilibrium, relying on kinetic barriers and fuel-driven cascades, it is also possible to amplify at thermodynamic equilibrium by shifting the energy landscape upon addition of an analyte. Equilibrium amplification is appealing because, in principle, the system can remain indefinitely in the untriggered state. In this work, we establish fundamental structural and thermodynamic limits on equilibrium-based amplification. We first prove that dimerization networks - systems restricted to complexes of at most two monomers - are inherently incapable of equilibrium amplification. This no-go theorem explains the absence of amplification in prior undercomplementary "strand commutation" designs. We then show that allowing trimeric complexes breaks this barrier. We propose an isometric trimer-based equilibrium amplifier whose output preserves the size of the input, enabling modular composition, and validate it experimentally, achieving an amplification factor close to the expected 2×. Finally, we derive universal thermodynamic bounds applicable regardless of complex size: the maximum amplification factor scales linearly with the free energy of interaction between the analyte and the amplifier components. For nucleic acid systems, this implies that the analyte length must grow linearly with the desired amplification factor, and that composing modular amplifiers yields diminishing returns for a fixed analyte. Together, these results delineate the structural and energetic boundaries of equilibrium amplification and rigorously justify the necessity of out-of-equilibrium approaches for achieving high gain.
Cite as

Hamidreza Akef, Chia-Yu Sung, Aneesh Vanguri, and David Soloveichik. Amplification at Equilibrium: Structural and Thermodynamic Limitations, and Implementation. In 32nd International Conference on DNA Computing and Molecular Programming (DNA 32). Leibniz International Proceedings in Informatics (LIPIcs), Volume 387, pp. 8:1-8:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{akef_et_al:LIPIcs.DNA.32.8,
  author =	{Akef, Hamidreza and Sung, Chia-Yu and Vanguri, Aneesh and Soloveichik, David},
  title =	{{Amplification at Equilibrium: Structural and Thermodynamic Limitations, and Implementation}},
  booktitle =	{32nd International Conference on DNA Computing and Molecular Programming (DNA 32)},
  pages =	{8:1--8:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-444-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{387},
  editor =	{Scalise, Dominic and Schweller, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.32.8},
  URN =		{urn:nbn:de:0030-drops-267789},
  doi =		{10.4230/LIPIcs.DNA.32.8},
  annote =	{Keywords: Equilibrium amplification, Dimerization networks, Strand commutation, Thermodynamics of amplification}
}
Document
DOI: 10.4230/LIPIcs.DNA.32.9
Thermodynamic Binding Networks Capture Equilibrium Monomer-Polymer Thermodynamics

Authors: And Kaan Ata Yilmaz, David Soloveichik, and Austin Luchsinger

Published in: LIPIcs, Volume 387, 32nd International Conference on DNA Computing and Molecular Programming (DNA 32) (2026)

Abstract
Thermodynamic Binding Networks (TBNs) are a minimal model for molecular thermodynamics. Despite their simplicity, the stable behavior of these systems can be unexpectedly nontrivial. To better understand the expressive power of the model, we compare TBNs with Thermodynamic Affinity Networks (TANs), a partition-scoring formalism in which polymer-level favorability is specified directly, rather than derived from domain-level interactions. We show that these two models are thermodynamically equivalent at the level of stable configurations: every TBN can be represented directly by a TAN, and every TAN can be indirectly realized by a TBN whose stable configurations map exactly to the stable configurations of the TAN. The key idea in the latter direction is to use auxiliary monomers that allow the system to convert polymer-level free-energy rewards specified by the TAN into entropic gains from separate complexes in the TBN. This correspondence shows that the local rules of TBNs do not limit their equilibrium expressive power nearly as much as one might expect. In this minimum-free-energy sense of equilibrium, TBNs capture the coarse-grained monomer-polymer thermodynamics formalized by TANs.
Cite as

And Kaan Ata Yilmaz, David Soloveichik, and Austin Luchsinger. Thermodynamic Binding Networks Capture Equilibrium Monomer-Polymer Thermodynamics. In 32nd International Conference on DNA Computing and Molecular Programming (DNA 32). Leibniz International Proceedings in Informatics (LIPIcs), Volume 387, pp. 9:1-9:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{yilmaz_et_al:LIPIcs.DNA.32.9,
  author =	{Yilmaz, And Kaan Ata and Soloveichik, David and Luchsinger, Austin},
  title =	{{Thermodynamic Binding Networks Capture Equilibrium Monomer-Polymer Thermodynamics}},
  booktitle =	{32nd International Conference on DNA Computing and Molecular Programming (DNA 32)},
  pages =	{9:1--9:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-444-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{387},
  editor =	{Scalise, Dominic and Schweller, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.32.9},
  URN =		{urn:nbn:de:0030-drops-267796},
  doi =		{10.4230/LIPIcs.DNA.32.9},
  annote =	{Keywords: Thermodynamic Binding Networks, Thermodynamic Affinity Networks, Equilibrium Thermodynamics}
}
Document
DOI: 10.4230/LIPIcs.DNA.32.10
Modularity of Signal Propagation Networks in the Thermodynamic Binding Network Model

Authors: And Kaan Ata Yilmaz and David Soloveichik

Published in: LIPIcs, Volume 387, 32nd International Conference on DNA Computing and Molecular Programming (DNA 32) (2026)

Abstract
The Thermodynamic Binding Network (TBN) model provides an equilibrium-based abstraction for molecular systems, but proving correctness of large networks built from individually verified modules remains difficult because modules can interact through shared binding-site types. We develop a method for proving correctness of modular TBNs by reducing a composition of arbitrarily many modules to a fixed coarse-grained TBN, computing the Hilbert basis of the reduced system, and lifting the resulting entropy bounds and polymer characterizations back to the original network. We apply this method to reversible signal-propagation modules: For the previously studied module implementing A+B ⟷ C, we show that stable configurations of an arbitrary network of such modules have the intended local structure, implying that firing an individual module preserves global stability. Under certain restrictions on the reaction set, these networks faithfully simulate a class of reversible chemical reaction networks: every bounded-length CRN execution can be realized by a height-2 path between stable TBN configurations, and any two stable TBN configurations map to CRN states in the same stoichiometric compatibility class. We further show that the same proof strategy extends to a novel module implementing reactions with two reactants and products like A+B ⟷ C+D.
Cite as

And Kaan Ata Yilmaz and David Soloveichik. Modularity of Signal Propagation Networks in the Thermodynamic Binding Network Model. In 32nd International Conference on DNA Computing and Molecular Programming (DNA 32). Leibniz International Proceedings in Informatics (LIPIcs), Volume 387, pp. 10:1-10:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{yilmaz_et_al:LIPIcs.DNA.32.10,
  author =	{Yilmaz, And Kaan Ata and Soloveichik, David},
  title =	{{Modularity of Signal Propagation Networks in the Thermodynamic Binding Network Model}},
  booktitle =	{32nd International Conference on DNA Computing and Molecular Programming (DNA 32)},
  pages =	{10:1--10:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-444-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{387},
  editor =	{Scalise, Dominic and Schweller, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.32.10},
  URN =		{urn:nbn:de:0030-drops-267809},
  doi =		{10.4230/LIPIcs.DNA.32.10},
  annote =	{Keywords: Thermodynamic Binding Networks, Chemical Reaction Networks, Modular Composition, Verification, Simulation}
}
Document
DOI: 10.4230/LIPIcs.DNA.32.12
Scalable Enumeration of Pareto-Optimal Polymers for Computing Equilibrium Concentrations

Authors: Archit Patil, Minki Hhan, and David Soloveichik

Published in: LIPIcs, Volume 387, 32nd International Conference on DNA Computing and Molecular Programming (DNA 32) (2026)

Abstract
Predicting equilibrium concentrations of molecular complexes is essential for verifying the behavior of engineered DNA systems. However, a finite set of monomer types can in principle generate infinitely many complexes. We study this candidate-enumeration problem in a geometry-free, domain-level abstraction called a domain-monomer system, generalizing Thermodynamic Binding Networks (TBNs) to the unsaturated setting where not every possible bond need be formed. We define Pareto-suboptimal polymers as those that can be split into non-interacting parts, and show that restricting attention to Pareto-optimal polymers is thermodynamically justified: no Pareto-suboptimal polymer appears in any minimum free-energy configuration, and the total equilibrium concentration of such polymers is small. We prove that there are finitely many Pareto-optimal polymers and exactly characterize them via a Hilbert basis computation, extending prior work from the saturated TBN model. To scale this approach to large systems, we develop a framework that restricts the number of different monomer types that a single polymer contains, and uses combinatorial covering designs to reduce the number of Hilbert basis computations required. We benchmark the method on several families of DNA molecular programming systems, demonstrating order-of-magnitude speedups over direct computation while recovering nearly all equilibrium-relevant polymers.
Cite as

Archit Patil, Minki Hhan, and David Soloveichik. Scalable Enumeration of Pareto-Optimal Polymers for Computing Equilibrium Concentrations. In 32nd International Conference on DNA Computing and Molecular Programming (DNA 32). Leibniz International Proceedings in Informatics (LIPIcs), Volume 387, pp. 12:1-12:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{patil_et_al:LIPIcs.DNA.32.12,
  author =	{Patil, Archit and Hhan, Minki and Soloveichik, David},
  title =	{{Scalable Enumeration of Pareto-Optimal Polymers for Computing Equilibrium Concentrations}},
  booktitle =	{32nd International Conference on DNA Computing and Molecular Programming (DNA 32)},
  pages =	{12:1--12:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-444-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{387},
  editor =	{Scalise, Dominic and Schweller, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.32.12},
  URN =		{urn:nbn:de:0030-drops-267823},
  doi =		{10.4230/LIPIcs.DNA.32.12},
  annote =	{Keywords: Molecular computation, Hilbert Basis, Thermodynamic Binding Network, covering design, equilibrium concentration}
}
Document
DOI: 10.4230/LIPIcs.DNA.31.10
Computing and Bounding Equilibrium Concentrations in Athermic Chemical Systems

Authors: Hamidreza Akef, Minki Hhan, and David Soloveichik

Published in: LIPIcs, Volume 347, 31st International Conference on DNA Computing and Molecular Programming (DNA 31) (2025)

Abstract
Computing equilibrium concentrations of molecular complexes is generally analytically intractable and requires numerical approaches. In this work we focus on the polymer-monomer level, where indivisible molecules (monomers) combine to form complexes (polymers). Rather than employing free-energy parameters for each polymer, we focus on the athermic setting where all interactions preserve enthalpy. This setting aligns with the strongly bonded (domain-based) regime in DNA nanotechnology when strands can bind in different ways, but always with maximum overall bonding - and is consistent with the saturated configurations in the Thermodynamic Binding Networks (TBNs) model. Within this context, we develop an iterative algorithm for assigning polymer concentrations to satisfy detailed-balance, where on-target (desired) polymers are in high concentrations and off-target (undesired) polymers are in low. Even if not directly executed, our algorithm provides effective insights into upper bounds on concentration of off-target polymers, connecting combinatorial arguments about discrete configurations such as those in the TBN model to real-valued concentrations. We conclude with an application of our method to decreasing leak in DNA logic and signal propagation. Our results offer a new framework for design and verification of equilibrium concentrations when configurations are distinguished by entropic forces.
Cite as

Hamidreza Akef, Minki Hhan, and David Soloveichik. Computing and Bounding Equilibrium Concentrations in Athermic Chemical Systems. In 31st International Conference on DNA Computing and Molecular Programming (DNA 31). Leibniz International Proceedings in Informatics (LIPIcs), Volume 347, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{akef_et_al:LIPIcs.DNA.31.10,
  author =	{Akef, Hamidreza and Hhan, Minki and Soloveichik, David},
  title =	{{Computing and Bounding Equilibrium Concentrations in Athermic Chemical Systems}},
  booktitle =	{31st International Conference on DNA Computing and Molecular Programming (DNA 31)},
  pages =	{10:1--10:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-399-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{347},
  editor =	{Schaeffer, Josie and Zhang, Fei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.31.10},
  URN =		{urn:nbn:de:0030-drops-238595},
  doi =		{10.4230/LIPIcs.DNA.31.10},
  annote =	{Keywords: Equilibrium concentrations, Thermodynamic Binding Networks, Monomer-polymer model, Detailed balance}
}
Document
DOI: 10.4230/LIPIcs.DNA.29.8
Thermodynamically Driven Signal Amplification

Authors: Joshua Petrack, David Soloveichik, and David Doty

Published in: LIPIcs, Volume 276, 29th International Conference on DNA Computing and Molecular Programming (DNA 29) (2023)

Abstract
The field of chemical computation attempts to model computational behavior that arises when molecules, typically nucleic acids, are mixed together. By modeling this physical phenomenon at different levels of specificity, different operative computational behavior is observed. Thermodynamic binding networks (TBNs) is a highly abstracted model that focuses on which molecules are bound to each other in a "thermodynamically stable" sense. Stability is measured based only on how many bonds are formed and how many total complexes are in a configuration, without focusing on how molecules are binding or how they became bound. By defocusing on kinetic processes, TBNs attempt to naturally model the long-term behavior of a mixture (i.e., its thermodynamic equilibrium). We study the problem of signal amplification: detecting a small quantity of some molecule and amplifying its signal to something more easily detectable. This problem has natural applications such as disease diagnosis. By focusing on thermodynamically favored outcomes, we seek to design chemical systems that perform the task of signal amplification robustly without relying on kinetic pathways that can be error prone and require highly controlled conditions (e.g., PCR amplification). It might appear that a small change in concentrations can result in only small changes to the thermodynamic equilibrium of a molecular system. However, we show that it is possible to design a TBN that can "exponentially amplify" a signal represented by a single copy of a monomer called the analyte: this TBN has exactly one stable state before adding the analyte and exactly one stable state afterward, and those two states "look very different" from each other. In particular, their difference is exponential in the number of types of molecules and their sizes. The system can be programmed to any desired level of resilience to false positives and false negatives. To prove these results, we introduce new concepts to the TBN model, particularly the notions of a TBN’s entropy gap to describe how unlikely it is to be observed in an undesirable state, and feed-forward TBNs that have a strong upper bound on the number of polymers in a stable configuration. We also show a corresponding negative result: a doubly exponential upper bound, meaning that there is no TBN that can amplify a signal by an amount more than doubly exponential in the number and sizes of different molecules that comprise it. We leave as an open question to close this gap by either proving an exponential upper bound, or giving a construction with a doubly-exponential difference between the stable configurations before and after the analyte is added. Our work informs the fundamental question of how a thermodynamic equilibrium can change as a result of a small change to the system (adding a single molecule copy). While exponential amplification is traditionally viewed as inherently a non-equilibrium phenomenon, we find that in a strong sense exponential amplification can occur at thermodynamic equilibrium as well - where the "effect" (e.g., fluorescence) is exponential in types and complexity of the chemical components.
Cite as

Joshua Petrack, David Soloveichik, and David Doty. Thermodynamically Driven Signal Amplification. In 29th International Conference on DNA Computing and Molecular Programming (DNA 29). Leibniz International Proceedings in Informatics (LIPIcs), Volume 276, pp. 8:1-8:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{petrack_et_al:LIPIcs.DNA.29.8,
  author =	{Petrack, Joshua and Soloveichik, David and Doty, David},
  title =	{{Thermodynamically Driven Signal Amplification}},
  booktitle =	{29th International Conference on DNA Computing and Molecular Programming (DNA 29)},
  pages =	{8:1--8:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-297-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{276},
  editor =	{Chen, Ho-Lin and Evans, Constantine G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.29.8},
  URN =		{urn:nbn:de:0030-drops-187917},
  doi =		{10.4230/LIPIcs.DNA.29.8},
  annote =	{Keywords: Thermodynamic binding networks, signal amplification, integer programming}
}
Document
DOI: 10.4230/LIPIcs.DNA.29.9
Optimal Information Encoding in Chemical Reaction Networks

Authors: Austin Luchsinger, David Doty, and David Soloveichik

Published in: LIPIcs, Volume 276, 29th International Conference on DNA Computing and Molecular Programming (DNA 29) (2023)

Abstract
Discrete chemical reaction networks formalize the interactions of molecular species in a well-mixed solution as stochastic events. Given their basic mathematical and physical role, the computational power of chemical reaction networks has been widely studied in the molecular programming and distributed computing communities. While for Turing-universal systems there is a universal measure of optimal information encoding based on Kolmogorov complexity, chemical reaction networks are not Turing universal unless error and unbounded molecular counts are permitted. Nonetheless, here we show that the optimal number of reactions to generate a specific count x ∈ ℕ with probability 1 is asymptotically equal to a "space-aware" version of the Kolmogorov complexity of x, defined as K̃s(x) = min_p {|p|/log|p| + log(space(𝒰(p))) : 𝒰(p) = x}, where p is a program for universal Turing machine 𝒰. This version of Kolmogorov complexity incorporates not just the length of the shortest program for generating x, but also the space usage of that program. Probability 1 computation is captured by the standard notion of stable computation from distributed computing, but we limit our consideration to chemical reaction networks obeying a stronger constraint: they "know when they are done" in the sense that they produce a special species to indicate completion. As part of our results, we develop a module for encoding and unpacking any b bits of information via O(b/log{b}) reactions, which is information-theoretically optimal for incompressible information. Our work provides one answer to the question of how succinctly chemical self-organization can be encoded - in the sense of generating precise molecular counts of species as the desired state.
Cite as

Austin Luchsinger, David Doty, and David Soloveichik. Optimal Information Encoding in Chemical Reaction Networks. In 29th International Conference on DNA Computing and Molecular Programming (DNA 29). Leibniz International Proceedings in Informatics (LIPIcs), Volume 276, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{luchsinger_et_al:LIPIcs.DNA.29.9,
  author =	{Luchsinger, Austin and Doty, David and Soloveichik, David},
  title =	{{Optimal Information Encoding in Chemical Reaction Networks}},
  booktitle =	{29th International Conference on DNA Computing and Molecular Programming (DNA 29)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-297-6},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{276},
  editor =	{Chen, Ho-Lin and Evans, Constantine G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.29.9},
  URN =		{urn:nbn:de:0030-drops-187920},
  doi =		{10.4230/LIPIcs.DNA.29.9},
  annote =	{Keywords: chemical reaction networks, Kolmogorov complexity, stable computation}
}
Document
DOI: 10.4230/LIPIcs.DNA.27.7
Molecular Machines from Topological Linkages

Authors: Keenan Breik, Austin Luchsinger, and David Soloveichik

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

Abstract
Life is built upon amazingly sophisticated molecular machines whose behavior combines mechanical and chemical action. Engineering of similarly complex nanoscale devices from first principles remains an as yet unrealized goal of bioengineering. In this paper we formalize a simple model of mechanical motion (mechanical linkages) combined with chemical bonding. The model has a natural implementation using DNA with double-stranded rigid links, and single-stranded flexible joints and binding sites. Surprisingly, we show that much of the complex behavior is preserved in an idealized topological model which considers solely the graph connectivity of the linkages. We show a number of artifacts including Boolean logic, catalysts, a fueled motor, and chemo-mechanical coupling, all of which can be understood and reasoned about in the topological model. The variety of achieved behaviors supports the use of topological chemical linkages in understanding and engineering complex molecular behaviors.
Cite as

Keenan Breik, Austin Luchsinger, and David Soloveichik. Molecular Machines from Topological Linkages. In 27th International Conference on DNA Computing and Molecular Programming (DNA 27). Leibniz International Proceedings in Informatics (LIPIcs), Volume 205, pp. 7:1-7:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{breik_et_al:LIPIcs.DNA.27.7,
  author =	{Breik, Keenan and Luchsinger, Austin and Soloveichik, David},
  title =	{{Molecular Machines from Topological Linkages}},
  booktitle =	{27th International Conference on DNA Computing and Molecular Programming (DNA 27)},
  pages =	{7:1--7:20},
  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/entities/document/10.4230/LIPIcs.DNA.27.7},
  URN =		{urn:nbn:de:0030-drops-146749},
  doi =		{10.4230/LIPIcs.DNA.27.7},
  annote =	{Keywords: chemical computation, mechanical computation, bioengineering, models of biochemistry, molecular machines, mechanical linkages, generic rigidity}
}
Document
DOI: 10.4230/LIPIcs.DNA.2020.4
CRNs Exposed: A Method for the Systematic Exploration of Chemical Reaction Networks

Authors: Marko Vasic, David Soloveichik, and Sarfraz Khurshid

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

Abstract
Formal methods have enabled breakthroughs in many fields, such as in hardware verification, machine learning and biological systems. The key object of interest in systems biology, synthetic biology, and molecular programming is chemical reaction networks (CRNs) which formalizes coupled chemical reactions in a well-mixed solution. CRNs are pivotal for our understanding of biological regulatory and metabolic networks, as well as for programming engineered molecular behavior. Although it is clear that small CRNs are capable of complex dynamics and computational behavior, it remains difficult to explore the space of CRNs in search for desired functionality. We use Alloy, a tool for expressing structural constraints and behavior in software systems, to enumerate CRNs with declaratively specified properties. We show how this framework can enumerate CRNs with a variety of structural constraints including biologically motivated catalytic networks and metabolic networks, and seesaw networks motivated by DNA nanotechnology. We also use the framework to explore analog function computation in rate-independent CRNs. By computing the desired output value with stoichiometry rather than with reaction rates (in the sense that X → Y+Y computes multiplication by 2), such CRNs are completely robust to the choice of reaction rates or rate law. We find the smallest CRNs computing the max, minmax, abs and ReLU (rectified linear unit) functions in a natural subclass of rate-independent CRNs where rate-independence follows from structural network properties.
Cite as

Marko Vasic, David Soloveichik, and Sarfraz Khurshid. CRNs Exposed: A Method for the Systematic Exploration of Chemical Reaction Networks. In 26th International Conference on DNA Computing and Molecular Programming (DNA 26). Leibniz International Proceedings in Informatics (LIPIcs), Volume 174, pp. 4:1-4:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{vasic_et_al:LIPIcs.DNA.2020.4,
  author =	{Vasic, Marko and Soloveichik, David and Khurshid, Sarfraz},
  title =	{{CRNs Exposed: A Method for the Systematic Exploration of Chemical Reaction Networks}},
  booktitle =	{26th International Conference on DNA Computing and Molecular Programming (DNA 26)},
  pages =	{4:1--4:25},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.2020.4},
  URN =		{urn:nbn:de:0030-drops-129574},
  doi =		{10.4230/LIPIcs.DNA.2020.4},
  annote =	{Keywords: molecular programming, formal methods}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.141
Hardness of Computing and Approximating Predicates and Functions with Leaderless Population Protocols

Authors: Amanda Belleville, David Doty, and David Soloveichik

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
Population protocols are a distributed computing model appropriate for describing massive numbers of agents with very limited computational power (finite automata in this paper), such as sensor networks or programmable chemical reaction networks in synthetic biology. A population protocol is said to require a leader if every valid initial configuration contains a single agent in a special "leader" state that helps to coordinate the computation. Although the class of predicates and functions computable with probability 1 (stable computation) is the same whether a leader is required or not (semilinear functions and predicates), it is not known whether a leader is necessary for fast computation. Due to the large number of agents n (synthetic molecular systems routinely have trillions of molecules), efficient population protocols are generally defined as those computing in polylogarithmic in n (parallel) time. We consider population protocols that start in leaderless initial configurations, and the computation is regarded finished when the population protocol reaches a configuration from which a different output is no longer reachable. In this setting we show that a wide class of functions and predicates computable by population protocols are not efficiently computable (they require at least linear time), nor are some linear functions even efficiently approximable. It requires at least linear time for a population protocol even to approximate division by a constant or subtraction (or any linear function with a coefficient outside of N), in the sense that for sufficiently small gamma > 0, the output of a sublinear time protocol can stabilize outside the interval f(m) (1 +/- gamma) on infinitely many inputs m. In a complementary positive result, we show that with a sufficiently large value of gamma, a population protocol can approximate any linear f with nonnegative rational coefficients, within approximation factor gamma, in O(log n) time. We also show that it requires linear time to exactly compute a wide range of semilinear functions (e.g., f(m)=m if m is even and 2m if m is odd) and predicates (e.g., parity, equality).
Cite as

Amanda Belleville, David Doty, and David Soloveichik. Hardness of Computing and Approximating Predicates and Functions with Leaderless Population Protocols. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 141:1-141:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{belleville_et_al:LIPIcs.ICALP.2017.141,
  author =	{Belleville, Amanda and Doty, David and Soloveichik, David},
  title =	{{Hardness of Computing and Approximating Predicates and Functions with Leaderless Population Protocols}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{141:1--141:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.141},
  URN =		{urn:nbn:de:0030-drops-75044},
  doi =		{10.4230/LIPIcs.ICALP.2017.141},
  annote =	{Keywords: population protocol, time lower bound, stable computation}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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