3 Search Results for "Petrack, Joshua"

Document
DOI: 10.4230/LIPIcs.DNA.32.7
Scaling up Thermodynamically Favoured Scaffolded DNA Computing by Sculpting the Energy Landscape

Authors: Joshua Petrack, Constantine G. Evans, Angel Cervera Roldan, Mahboobeh Enayati, and Damien Woods

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

Abstract
Thermodynamically favoured molecular computation offers advantages over more typical out-of-equilibrium computing, including simpler experimental protocols and automatic error correction. But as systems scale to large sizes the number of states increases dramatically, increasing the need for efficiently navigable energy landscapes. We give results in two theoretical models of Scaffolded DNA Computing (SDC), a recently implemented form of thermodynamically favoured DNA computing [Stérin, Eshra et al, bioRχiv 2025]. We show their computational power is characterised by logarithmic space complexity classes, meaning they are expressive at scale. Our first energy landscape result is an exact relation between the probability of target configurations (outputs), temperature and DNA sequence domain length, showing that domain length merely logarithmic in scaffold length is sufficient for the probability of the target configuration to outcompete all off-target structures. We show that even in the presence of imperfect/unequal binding strength scaffold domains we still achieve good kinetics: O(N²) or O(N³) expected completion time, depending on model assumptions, and there are even narrow conditions that yield fast O(N)-time kinetics. Finally, we address a thorny scaling problem: SDC outputs often have repeated compute domains and any binding energy variances get exaggerated under repetition making errors favourable, but we give a construction that reprograms the energy landscape to convert such a non-isoenergetic system into one with almost perfectly isoenergetic energy plateaus. We also show that systems maintain good (polynomial-time) kinetics, even in the face of a poor (uphill) scaffold energy landscape. These results give a roadmap for scaling up the SDC while highlighting the role kinetics and energy landscape programming could play in thermodynamically-favoured computing more generally.
Cite as

Joshua Petrack, Constantine G. Evans, Angel Cervera Roldan, Mahboobeh Enayati, and Damien Woods. Scaling up Thermodynamically Favoured Scaffolded DNA Computing by Sculpting the Energy Landscape. In 32nd International Conference on DNA Computing and Molecular Programming (DNA 32). Leibniz International Proceedings in Informatics (LIPIcs), Volume 387, pp. 7:1-7:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{petrack_et_al:LIPIcs.DNA.32.7,
  author =	{Petrack, Joshua and Evans, Constantine G. and Cervera Roldan, Angel and Enayati, Mahboobeh and Woods, Damien},
  title =	{{Scaling up Thermodynamically Favoured Scaffolded DNA Computing by Sculpting the Energy Landscape}},
  booktitle =	{32nd International Conference on DNA Computing and Molecular Programming (DNA 32)},
  pages =	{7:1--7:22},
  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.7},
  URN =		{urn:nbn:de:0030-drops-267776},
  doi =		{10.4230/LIPIcs.DNA.32.7},
  annote =	{Keywords: Thermodynamically favoured computing, molecular programming, DNA computing, kinetics, computational power, Scaffolded DNA Computer}
}
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}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 1 2025
  • 1 2023

  • Refine by Author
  • 2 Petrack, Joshua
  • 2 Soloveichik, David
  • 1 Akef, Hamidreza
  • 1 Cervera Roldan, Angel
  • 1 Doty, David
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 3 Theory of computation → Models of computation
  • 1 Applied computing → Chemistry
  • 1 Applied computing → Physics
  • 1 Theory of computation → Design and analysis of algorithms

  • Refine by Keyword
  • 1 DNA computing
  • 1 Detailed balance
  • 1 Equilibrium concentrations
  • 1 Monomer-polymer model
  • 1 Scaffolded DNA Computer
  • Show More...

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