A while ago I blogged about David Soloveichik’s talk at this workshop:
• Programming with Chemical Reaction Networks: Mathematical Foundations, Banff International Research Station, 8-13 June 2014.
Now the slides for his talk are available:
• David Soloveichik, U.C. San Francisco, The computational power of chemical reaction networks.
And now I’d like to tell you about three more talks!
The first two are about ways one chemical reaction network can simulate another. This is important for a couple of reasons. First, in biology, a bunch of different chemical reactions can ‘accomplish the same task’—and we’d like to make this idea precise. That’s what Luca Cardelli spoke about. Second, people trying to do computation with chemistry are starting to simulate quite general reactions using DNA! That’s what Sheung Woo Shin spoke about.
Luca Cardelli was at Oxford when I was visiting this spring, but unfortunately I didn’t meet him! He works for Microsoft on the interface of biology and computation. At Banff, he talked about ways one chemical reaction network can simulate another. His slides are here:
• Luca Cardelli, Morphisms of reaction networks.
He has a paper that gives a more detailed explanation of these ideas:
• Luca Cardelli, Morphisms of reaction networks that couple structure to function.
Here is my own disorganized explanation… with lots of informative but confusing digressions. A population protocol is a chemical reaction with only 2-in, 2-out reactions. For example, this paper presents a population protocol that does ‘approximate majority detection':
• Dana Angluin, James Aspnes, and David Eisenstat, A simple population protocol for fast robust approximate majority, Distributed Computing 21 (2008), 87–102.
What’s the idea? We start with two kinds of molecules, say ’s and ’s, and we want to see which one is in the majority, so we run these chemical reactions:
See? All the reactions have 2 molecules going in and 2 going out. The molecules act as ‘undecided voters’ who become either an or a depending on who they meet first.
If we start with about molecules, in time these reactions are very likely to convert all ’s and ’s to whatever kind of molecule was in the majority initially… at least if the gap in the number of ’s and ’s is big enough.
Here’s another population protocol that also does the job:
And here’s a proof that one of these algorithms actually works—most of the time, when the initial difference in populations is big enough:
• Etienne Perron, Dinkar Vasudevan, and Milan Vojonvic, Using three states for binary consensus on complete graphs, Technical Report, MSR-TR-2008-114, Microsoft, September 2008.
If we use a discrete-time formalism to describe the dynamics, the proof seems to get harder. See the paper by Angluin, Aspnes, and Eisenstat for the only known proof!
Anyway, Luca Cardelli is interested in chemical reaction networks actually found in biology. This approximate majority algorithm is seen quite clearly in a certain biological system: a certain ‘epigenetic switch’. However, it is usually ‘obfuscated’ or ‘encrypted': hidden in a bigger, more complicated chemical reaction network. For example, see:
• Luca Cardelli and Attila Csikász-Nagy, The cell cycle switch is approximate majority obfuscated, Scientific Reports 2 (2012).
This got him interested in developing a theory of morphisms between reaction networks, which could answer questions like: When can one CRN emulate another? But these questions turn out to be much easier if we use the rate equation than with the master equation. So, he asks: when can one CRN give the same rate equation as another?
He found a sufficient condition that’s ‘purely syntactic': you can tell if it holds by looking at the reaction networks, regardless of the rate constants.
Here’s the idea. We say one network emulates another if for any rate constants of the second, we can find rate constants for the first that makes its rate equation have solutions exactly mimicking that of the second, but where several species in the first correspond to one in the second.
For this to make sense, we assume there is a map sending:
• species to species
• reactions to reactions
In a chemical reaction network homomorphism, the map on reactions is determined by the map on species in the obvious way. For example, if species is sent to and species is sent to then the reaction
is sent to the reaction
In this situation, to make the first network emulate the second, we need to set equal the initial concentrations of all species in the inverse image of a given species.
A reactant homomorphism from one chemical reaction network to another is more general: it sends species to species, and for any reaction in the first chemical reaction network with input
there’s a reaction in the second with input
(Reactant is another name for input.)
A stoichiomorphism is a kind of morphism that takes rate constants into account. See Cardelli’s paper for the definition.
The main theorem: given a stoichiomorphism from one chemical reaction network to another that’s also a reactant homomorphism, then the first emulates the second.
For a better explanation, read his paper! Here’s a cool picture from his paper showing a bunch of chemical reaction networks including the approximate majority network (labelled AM), many of which show up in biology, and morphisms between them:
Click to enlarge! These chemical reaction networks are drawn in a special style: as influence networks, consisting of ‘gates’ where process activates or deactivates another. Each gate is a chemical reaction network of a certain form, schematically like this:
where the forward reactions are catalyzed by one chemical and the reverse reactions are catalyzed by another. A gate is like a switch that can be turned on or off.
While listening to this talk, I thought the way in which one CRN emulates another in Cardelli’s formalism looks awfully similar to the way one dynamical system emulates another in Eugene Lerman’s formalism:
• Eugene Lerman, Networks of dynamical systems, Azimuth, 18 March 2014.
The following picture from Cardelli’s paper shows that one of his morphisms of reaction networks is like ‘covering map’. This reminds me a lot of what’s happening in Lerman’s work.
Again, click to enlarge!
Seung Woo Shin
Seung Woo Shin was actually Brendan Fong’s roommate at the National University of Singapore while Brendan was working with me on chemical reaction networks. Apparently they never talked about their work!
Shin spoke about some other concepts of ‘morphism’ between chemical reaction networks. These other concepts do not involve reaction rates, just which chemicals can turn into which. You can see his slides here:
• Seung Woo Shin, Verifying CRN implementations.
and read his thesis for more details:
• Seung Woo Shin, Compiling and verifying DNA-based chemical reaction network implementations, Masters thesis, Caltech, 2012.
Abstract: One goal of molecular programming and synthetic biology is to build chemical circuits that can control chemical processes at the molecular level. Remarkably, it has been shown that synthesized DNA molecules can be used to construct complex chemical circuits that operate without any enzyme or cellular component. However, designing DNA molecules at the individual nucleotide base level is often difficult and laborious, and thus chemical reaction networks (CRNs) have been proposed as a higher-level programming language. So far, several general-purpose schemes have been described for designing synthetic DNA molecules that simulate the behavior of arbitrary CRNs, and many more are being actively investigated.
Here, we solve two problems related to this topic. First, we present a general-purpose CRN-to-DNA compiler that can apply user-defined compilation schemes for translating formal CRNs to domain-level specifications for DNA molecules. In doing so, we develop a language in which such schemes can be concisely and precisely described. This compiler can greatly reduce the amount of tedious manual labor faced by researchers working in the field. Second, we present a general method for the formal verification of the correctness of such compilation. We first show that this problem reduces to testing a notion of behavioral equivalence between two CRNs, and then we construct a mathematical formalism in which that notion can be precisely defined. Finally, we provide algorithms for testing that notion. This verification process can be thought of as an equivalent of model checking in molecular computation, and we hope that the generality of our verification techniques will eventually allow us to apply them not only to DNA-based CRN implementations but to a wider class of molecular programs.
His thesis built on this earlier paper:
• David Soloveichik, Georg Seelig and Erik Winfree, DNA as a universal substrate for chemical kinetics, Proceedings of the National Academy of Sciences (2010).
I think this work is fascinating and deeply related to category theory, so I talked to Shin and Winfree about it, and this is what we came up with:
• CRN equivalences: progress report.
This is one of several reports on progress people at the workshop made on various open problems.
Brendan Fong and I wrote about David Anderson’s work in Part 9 of the network theory series. It’s so impressive that I expected him to be older… older than me, I guess. He’s not!
In his tutorial, he gave an overview of chemical reaction networks with an emphasis on the deficiency zero theorem. Since many people were puzzled by the ‘deficiency’ concept, they asked lots of questions. But I’ve already explained that idea in Part 21. So, I’ll just mention a couple of cool theorems he told us about!
Theorem (Horn and Jackson). If a reaction network has a complex balanced equilibrium, then:
1. It has no equilibria that are not complex balanced.
2. The reaction network must be weakly reversible.
3. Every stochiometric compatibility class contains precisely one complex balanced equilibrium.
I should have known this, since this work is classic. But I don’t think I knew that the existence of one complex balanced equilibrium implied all this stuff!
He also mentioned this paper:
• Guy Shinar and Martin Feinberg, Structural sources of robustness in biochemical reaction networks, Science (2010).
which contains this amazing theorem:
Theorem (Shinar and Feinberg). Suppose there is a chemical reaction network such that:
1. its deficiency equals one;
2. it has a positive steady state;
3. it has two “non-terminal complexes” that differ only in one species (“Non-terminal” is a concept that’s easier to explain with a picture of a reaction network).
Then the species is absolutely robust: with any initial conditions, the rate equation will approach an equilibrium where the concentration of approaches a specific fixed value independent of the initial conditions!
However, things work very differently if we treat the system stochastically, using the master equation:
• David F. Anderson, German A. Enciso and Matthew D. Johnston, Stochastic analysis of biochemical reaction networks with absolute concentration robustness.
A lot more happened at this workshop! There was a huge amount of discussion of the leader election problem, which is about how to cook up chemical reactions that create a ‘leader': a single molecule of some sort.
• Leader election: the problem, and references.
• Leader election: progress report.
As I explained before, David Soloveichik talked about various forms of digital computation with chemical reaction networks. David Doty talked about the very important flip side of the coin: analog computation.
• David Doty, Rate-independent computation by real-valued chemistry.
There were also great talks by Lulu Qian and Erik Winfree, which I won’t try to summarize. Qian does a lot of work in the lab making things actually happen, so if you’re a practical sort this is the talk to look at:
• Lulu Qian, Implementing complex CRNs with modular DNA components.
All in all, a very stimulating workshop. The diversity of things one can ask about chemical reaction networks is quite exciting!