CaltechAUTHORS
  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. https://resolver.caltech.edu/CaltechAUTHORS:20141218-112132219

[img]
Preview
PDF - Submitted Version
See Usage Policy.

1347Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20141218-112132219

Abstract

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
http://dx.doi.org/10.1007/s11047-013-9393-6DOIArticle
http://link.springer.com/article/10.1007/s11047-013-9393-6PublisherArticle
http://arxiv.org/abs/1204.4176arXivDiscussion Paper
http://www.ncbi.nlm.nih.gov/pmc/articles/PMC4221813/PubMed CentralArticle
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.
Funders:
Funding AgencyGrant Number
NSF0832824
NSC101-2221-E-002-122-MY3
NSF1019343
NSFCCF-1219274
NSFCCF-1162589
NIGMSP50 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:https://resolver.caltech.edu/CaltechAUTHORS:20141218-112132219
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:03 Oct 2019 07:46

Repository Staff Only: item control page