A Caltech Library Service

Deterministic function computation with chemical reaction networks

Chen, Ho-Lin and Doty, David and Soloveichik, David (2014) Deterministic function computation with chemical reaction networks. Natural Computing, 13 (4). pp. 517-534. ISSN 1567-7818. PMCID PMC4221813. doi:10.1007/s11047-013-9393-6.

[img] PDF - Accepted Version
See Usage Policy.

PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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 (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 multi-dimensional 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^l|f(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:
URLURL TypeDescription ReadCube access Paper CentralArticle ItemBook Chapter
Doty, David0000-0002-3922-172X
Soloveichik, David0000-0002-2585-4120
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 101-2221-E-002-122-MY3, the second and third authors were supported by a Computing Innovation Fellowship under NSF Grant 1019343. The second author was supported by NSF Grants CCF-1219274 and CCF-1162589. The third author was supported by NIGMS Systems Biology Center Grant P50 GM081879.
Funding AgencyGrant Number
National Science Council (Taipei)101-2221-E-002-122-MY3
NIHP50 GM081879
Subject Keywords:Molecular programming, Stochastic chemical kinetics, Distributed computing, Population protocols, Semilinear functions
Issue or Number:4
PubMed Central ID:PMC4221813
Record Number:CaltechAUTHORS:20141218-112132219
Persistent URL:
Official Citation:Chen, H., Doty, D. & Soloveichik, D. Deterministic function computation with chemical reaction networks. Nat Comput 13, 517–534 (2014).
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:53019
Deposited By: Ruth Sustaita
Deposited On:18 Dec 2014 19:41
Last Modified:10 Nov 2021 19:46

Repository Staff Only: item control page