Search Results

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.

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.