Dave Doty (CalTech) talk - Deterministic Function Computation with Chemical Reaction Networks


Deterministic Function Computation with Chemical Reaction Networks


Chemical reaction networks (CRNs) formally model chemistry in a well-mixed solution.  CRNs are widely used to describe information processing occurring in natural cellular regulatory networks, and with upcoming advances in synthetic biology, CRNs are a promising language for the design of artificial molecular control circuitry. Nonetheless, despite the widespread use of CRNs in the natural sciences, the range of computational behaviors exhibited by CRNs is not well understood.  CRNs have been shown to be efficiently Turing-universal when allowing for a small probability of error.  CRNs that are guaranteed to converge on a correct answer, on the other hand, have been shown to decide only the semilinear predicates.

We introduce the notion of function, rather than predicate, computation by representing the output of a function f:N^k --> N^l by a count of some molecular species, i.e., if the CRN starts with x_1,...,x_k molecules of some "input" species X1,...,Xk, the CRN is guaranteed to converge to having f(x_1,...,x_k) molecules of the "output" species Y1,...,Yl.  We show that a function f is deterministically computed by a CRN if and only if its graph { (x,y) | f(x) = y } is a semilinear set.  This implies, for instance, that no chemicals could be designed that are guaranteed to transform n copies of molecule X into n^2 copies of molecule Y, although this is possible to achieve with a small probability of error.

We draw the conclusion that the use of randomness is even more crucial to sophisticated molecular computation than it is to conventional randomized algorithm design.


David Doty received his Ph.D. in Computer Science at Iowa State University in 2009, supervised by Jack Lutz.  His thesis focused on applying the theory of computation to theoretical problems in molecular self-assembly. He is currently a postdoc for Erik Winfree at the California Institute of Technology, where he proves theorems related to molecular computation and conducts physical experiments implementing molecular computation with DNA.

Site Categories