Chen, HoLin and Doty, David and Soloveichik, David (2014) Deterministic function computation with chemical reaction networks. Natural Computing, 13 (4). pp. 517534. ISSN 15677818. PMCID PMC4221813. http://resolver.caltech.edu/CaltechAUTHORS:20141218112132219

PDF
 Submitted Version
See Usage Policy. 1347Kb 
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20141218112132219
Abstract
Chemical reaction networks (CRNs) formally model chemistry in a wellmixed 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 Turinguniversal (i.e., able to simulate arbitrary algorithms) 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 (a multidimensional generalization of “eventually periodic” sets). 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 X_1,…,X_k, the CRN is guaranteed to converge to having f(x_1,…,x_k) molecules of the “output” species Y_1,…,Y_l . We show that a function f:N^k→N^l is deterministically computed by a CRN if and only if its graph {(x,y)∈N^k×N^lf(x)=y} is a semilinear set. Finally, we show that each semilinear function f (a function whose graph is a semilinear set) can be computed by a CRN on input x in expected time O(polylog∥x∥_1).
Item Type:  Article  

Related URLs: 
 
Additional Information:  © 2013 Springer Science. Published online: 3 September 2013. We thank Damien Woods and Niranjan Srinivas for many useful discussions, Monir Hajiaghayi for pointing out a problem in an earlier version of this paper, and anonymous reviewers for helpful suggestions. The first author was supported by the Molecular Programming Project under NSF Grant 0832824 and NSC grant 1012221E002122MY3, the second and third authors were supported by a Computing Innovation Fellowship under NSF Grant 1019343. The second author was supported by NSF Grants CCF1219274 and CCF1162589. The third author was supported by NIGMS Systems Biology Center Grant P50 GM081879.  
Funders: 
 
Subject Keywords:  Molecular programming, Stochastic chemical kinetics, Distributed computing, Population protocols, Semilinear functions  
PubMed Central ID:  PMC4221813  
Record Number:  CaltechAUTHORS:20141218112132219  
Persistent URL:  http://resolver.caltech.edu/CaltechAUTHORS:20141218112132219  
Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided.  
ID Code:  53019  
Collection:  CaltechAUTHORS  
Deposited By:  Ruth Sustaita  
Deposited On:  18 Dec 2014 19:41  
Last Modified:  18 Dec 2014 19:41 
Repository Staff Only: item control page