Robust CRNs

(See problem statement already on wiki - we focused on HQ2.)

The actual problems faced by strand-displacement circuits include "bad gates", which consume reactants but don't produce products, and "leak" reactions, where a gate releases some or all of its products without some or all of the intended reactants. Rather than attempt to characterize the unintended reactions, we tried to solve the most general case: design formal CRNs that work robustly in the presence of $\emptyset \xrightarrow{\varepsilon_1} X$ (leak reactions) and $X \xrightarrow{\varepsilon_1} \emptyset$ (bad gates) for all species $X$. Obviously, such a CRN cannot work with probability 1, and we concluded that trying to define robustness for stabilizing CRNs was not meaningful when unintended reactions can change the output after the intended computation has long since finished. Thus we narrowed our focus to CRNs which "halt", i.e. produce either one (or more) molecules of some species $Y$ or one (or more) molecules of some species $N$, but not both, and after one has been produced, the computation is finished, and produce the correct molecule with probability $1 - \delta$. This class of CRNs is known to be Turing-universal. Our question then becomes, in terms of $\varepsilon_1$ and $\varepsilon_2$, what is the new probability of correctness, and how high can we get it?

To begin with, we focused on a simplified version of the register machine by Soloveichik et. al., which proved that probabilistically correct halting CRNs are Turing-universal. This register machine is particularly vulnerable to implementation errors, as it requires exactly one copy of one state molecule and and changes in the count of a register molecule can cause drastic changes in the computation in general. We approached from two directions. First, we asked how long the computation was likely to go without a single leak reaction happening, and second, we asked whether the CRN could be modified to make it tolerant to and/or correct for leaks.

In approaching the first, we considered a simple 7( plus halt)-instruction register machine that takes three inputs in registers $x$, $y$, and $w$, adds $x+y$ and stores the result in a fourth register $z$, then compares $z$ and $w$ and accepts if and only if $z = w$. Note that in the original construction, there are two timescales for reactions: increment and decrement operations are done at a fast timescale, while the jump instruction, which is meant to be done instead of a decrement operation only when the register to be decremented is 0, is done at a slower timescale to make it unlikely to happen when the register is nonzero. (This is the original source of error in the register machine CRN.) We labelled the fast rate 1 and the slower rate $\tau$. When we calculated the expected time for the register machine to complete, it was $O(x + y + w + \frac{1}{\tau})$ (assuming the register machine behaves correctly). In particular, the correct computation does either 3 or 4 reactions with rate $\tau$. We considered the case where $\frac{1}{\tau} >> x + y + w$, in which case the expected time is approximately $\frac{4}{\tau}$, and for $\tau \approx 10^{-2}$ (which we felt to be a reasonable value), we calculated that $\varepsilon_i \approx 10^{-4}$ was sufficient for there to exist a time $T$ such that there is a probability of $.95$ that the register machine computation finishes by time $T$ (conditional on computing correctly) and a probability of $.95$ that no unintended reactions occur before time $T$. Experimental strand displacement systems typically have maximum rate constants on the order of $10^6$ and unintended reactions on the order of $10^1$, which allows us to make $\tau \approx 10^4$ while satisfying the bound we calculated for this particular register machine. This is heartening, since it shows that the current strand displacement technology has reduced unintended reactions to a point comparable to what is necessary for low-error-probability register machine computation. However, it is also somewhat worrying, since the case of a register machine's computation being $O(\frac{1}{\tau})$ is rare. This particular computation does so since it has no nested loops, i.e. no DECJUMP instruction whose JUMP part is taken at least once each loop controlled by another DECJUMP instruction. Other register machines might have expected time $O(\frac{x}{\tau})$ or worse. (We conjecture that our assumption that $\frac{1}{\tau}$ dominates the register inputs is necessary to minimize the register machine's natural error probability.)

We then considered whether we could modify the register machine CRN to be resistant to unintended reactions and/or detect and correct them when they happen. In this particular case, the two major points of failure are the single-copy state molecules and the need for exact counts of register molecules. Our solution was to make the molecules redundant to some degree, replacing one state molecule with two (copies of the same state molecule) and one register molecule with 3. So instead of having one copy of state molecule $S_i$ and $x$ molecules of register $r$, we would have two molecules of $S_i$ and $3x+1$ of $r$. Each reaction would consume or produce 2 state molecules instead of !, and 3 register molecules instead of 1; for example, $2 S_1 + 3 x \rightarrow 2 S_2$. Then producing or consuming one register molecule will not change the value (as far as the CRN can tell), and producing one state molecule will be irrelevant since it cannot react with anything. We can furthermore add reactions $S_i + S_i + S_j \rightarrow S_i + S_i$ to consume incorrectly produced states, and once we can consume incorrect states, we can add $S_i \xrightarrow S_i + S_i$, which if one state molecule has been improperly consumed, can reproduce it, while if it fires when unnecessary the extra state molecule will be consumed by $S_j + S_j + S_i \xrightarrow S_j + S_j$ after two of the three molecules have changed state. All of these are potential ideas, however it is possible that any of them introduce more problems than they solve. In particular, we are now using 5-molecular reactions, whose expected times scale with $V^4$. It is unclear whether the error-correction capabilities make up for the increase in computation time which causes an increased probability that a leak reaction will happen.

Finally, we proposed some other aspects of the problem that we did not focus on. Some systems, such as oscillators, are better modelled with deterministic ODEs due to using a large number of molecules, and it would be worth considering how unintended reactions affect those. We could have also considered the specific types of leak typical in strand displacement systems, where leak reactions don't produce any species with uniform probability, but are more likely to for example produce the products of a bimolecular reaction with only the second reaction. As a more specific class of leak, this might be easier to give an error bound for, but it would also invalidate (for example) the error-detection and error-tolerance systems we proposed for the register machine. There are a number of remaining questions which we intend to continue working on in the future.