SCIENCE@home

Deterministic function computation with chemical reaction networks

Ho-Lin Chen,David Doty,D. Soloveichik

Published 2012 in Natural Computing

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:{\mathbb{N}}^k\to{\mathbb{N}}^l}$$f:Nk→Nl by a count of some molecular species, i.e., if the CRN starts with $$x_1,\ldots,x_k$$x1,…,xk molecules of some “input” species $$X_1,\ldots,X_k, $$X1,…,Xk, the CRN is guaranteed to converge to having $$f(x_1,\ldots,x_k)$$f(x1,…,xk) molecules of the “output” species $$Y_1,\ldots,Y_l$$Y1,…,Yl. We show that a function $${f:{\mathbb{N}}^k \to {\mathbb{N}}^l}$$f:Nk→Nl is deterministically computed by a CRN if and only if its graph $${\{({\bf x, y}) \in {\mathbb{N}}^k \times {\mathbb{N}}^l | f({\bf x}) = {\bf y}\}}$${(x,y)∈Nk×Nl|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(\hbox{polylog} \|{\bf x}\|_1)$$O(polylog∥x∥1).

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-31 of 31 references · Page 1 of 1

CITED BY

Showing 1-100 of 159 citing papers · Page 1 of 2

12
Next