Robust Biomolecular Finite Automata

This poster presents a uniform method for translating an arbitrary nondeterministic nite automaton (NFA) into a deterministic mass action chemical reaction network (CRN) that simulates it. The CRN receives its input as a continuous time signal consisting of concentrations of chemical species that vary to represent the NFA's input string in a natural way. The CRN exploits the inherent parallelism of chemical kinetics to simulate the NFA in real time, and its size is linear in the number of states of the NFA. The compiler of Chen et al. (2013) would then translate this into a DNA strand displacement network whose size is also linear in the size of the NFA. Our translation thus appears to make small NFAs implementable in laboratories now and NFAs of modest size implementable in the near future.

Most importantly, our CRN's correct implementation of the NFA is robust with respect to small perturbations of four things, namely, its input signal, the initial concentrations of its species, its output signal (acceptance or rejection of its input string), and the rate constants of its reactions.

In summary we have identi ed a rich and useful class of computations that can be implemented robustly in the molecular world, i.e., implemented in such a way that they will provably perform correctly, even when crucial parameters are perturbed by small amounts. This robustness is important, because processes that can be implemented, but only with inordinately precise control of parameters, are inherently unreliable and hence inherently unsafe in many envisioned applications.

This research was supported in part by National Science Foundation Grants 1247051 and 1545028.