Speaker: Prof David Doty, Department of Computer Science, University of California, Davis, USA.
Title: "Digging (energy) wells for unknown substances: Programming substrate-independent energy barriers in catalytic chemical reactions."
Abstract: A well-mixed chemical system can be described with abstract chemical reactions such as A + C ↔ B + C. Long used in natural science to study the properties of natural molecules, this model is now also used as programming language for describing the desired behavior of synthetic molecules, based on recent experimental advances in DNA nanotechnology enabling arbitrary chemical reactions to be implemented with DNA. The reaction has a catalyst C that enables A to transform into B and vice versa. But what remains hidden at this level of abstraction is a well-known chemical constraint: if the reaction A + C ↔ B + C is possible, then the uncatalyzed reaction A ↔ B must also be possible, no matter the exact substances.
We study the problem of making the uncatalyzed reaction A ↔ B arbitrarily unlikely, no matter the exact substances. We use the model of thermodynamic binding networks to model chemical systems in a "substrate independent" way, showing programmable energy barriers arising solely from the thermodynamic driving forces of bond formation and the so-called "configurational entropy" of forming separate complexes.
We show that for any n ∈ ℕ+, there is a network with two stable states A and B, and the only way to change between A and B is to merge together n separate complexes (an energy barrier of n), an event whose probability is exponentially small as n grows. Further, we show that a catalyst monomer C lowers the energy barrier to 1: A, with the help of C, can change into B by a sequence of (high-probability) bimolecular reactions where two complexes merge together, exchange bonds, and then split apart. We extend this to show a network with arbitrarily many stable states, with catalysts possible between any pair A,B of them, which maintain a large energy barrier to change to or from any state other than A or B. A long-term goal is to design real chemicals implementing the autocatalytic reaction A + C ↔ C + C with a large barrier to A ↔ C, enabling one to detect, in a solution containing billions of A molecules, the presence or absence of a single C, with arbitrarily low probability of a false positive.
Our results borrow interesting techniques from combinatorics and coding theory. One formulation of our question turns out to be equivalent to the mutually orthogonal Latin squares problem studied by Euler, known also (slightly generalized) as the Social Golfer Problem: say n=4, can sixteen (n2) golfers play in foursomes (n-somes) for five (n+1) days, so that no pair of golfers play together on two different days?