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. https://resolver.caltech.edu/CaltechAUTHORS:20141218-112132219
![]() |
PDF
- Accepted Version
See Usage Policy. 1MB | |
|
PDF
- Submitted Version
See Usage Policy. 1MB |
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: |
| ||||||||||||||||||
ORCID: |
| ||||||||||||||||||
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: |
| ||||||||||||||||||
Subject Keywords: | Molecular programming, Stochastic chemical kinetics, Distributed computing, Population protocols, Semilinear functions | ||||||||||||||||||
Issue or Number: | 4 | ||||||||||||||||||
PubMed Central ID: | PMC4221813 | ||||||||||||||||||
DOI: | 10.1007/s11047-013-9393-6 | ||||||||||||||||||
Record Number: | CaltechAUTHORS:20141218-112132219 | ||||||||||||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20141218-112132219 | ||||||||||||||||||
Official Citation: | Chen, H., Doty, D. & Soloveichik, D. Deterministic function computation with chemical reaction networks. Nat Comput 13, 517–534 (2014). https://doi.org/10.1007/s11047-013-9393-6 | ||||||||||||||||||
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: | 10 Nov 2021 19:46 |
Repository Staff Only: item control page