Deterministic Function Computation with Chemical Reaction Networks

DOI10.1007/978-3-642-32208-2_3zbMATH Open1330.68070arXiv1204.4176OpenAlexW1871080051MaRDI QIDQ5200596FDOQ5200596

David Doty, David Soloveichik, Ho-Lin Chen

Publication date: 6 November 2012

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

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 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. 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 n_1,...,n_k molecules of some "input" species X1,...,Xk, the CRN is guaranteed to converge to having f(n_1,...,n_k) molecules of the "output" species Y1,...,Yl. We show that a function f:N^k --> N^l is deterministically computed by a CRN if and only if its graph {(x,y) | f(x) = y} is a semilinear set. Furthermore, each semilinear function f can be computed on input x in expected time O(polylog(|x|)).

Full work available at URL: https://arxiv.org/abs/1204.4176

Recommendations

• Deterministic function computation with chemical reaction networks
• Composable Computation in Discrete Chemical Reaction Networks
• Composable computation in discrete chemical reaction networks
• Computation with finite stochastic chemical reaction networks
• Composable rate-independent computation in continuous chemical reaction networks
• Rate-independent computation in continuous chemical reaction networks
• Programming discrete distributions with chemical reaction networks
• Programming discrete distributions with chemical reaction networks
• Compiling elementary mathematical functions into finite chemical reaction networks via a polynomialization algorithm for ODEs
• The computational capability of chemical reaction automata

Mathematics Subject Classification ID

Biochemistry, molecular biology (92C40) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Cited In (24)

• Extracting reaction systems from function behavior
• Theory of reaction automata: a survey
• Speed Faults in Computation by Chemical Reaction Networks
• The computational capability of chemical reaction automata
• Leaderless Deterministic Chemical Reaction Networks
• Compiling elementary mathematical functions into finite chemical reaction networks via a polynomialization algorithm for ODEs
• Deterministic function computation with chemical reaction networks
• Reachability bounds for chemical reaction networks and strand displacement systems
• Decomposition and factorization of chemical reaction transducers
• Leaderless deterministic chemical reaction networks
• Testing binomiality of chemical reaction networks using comprehensive Gröbner systems
• Functional Analysis of Large-Scale DNA Strand Displacement Circuits
• Modular Verification of DNA Strand Displacement Networks via Serializability Analysis
• Modular verification of chemical reaction network encodings via serializability analysis
• Synthesizing and Tuning Chemical Reaction Networks with Specified Behaviours
• Composable computation in discrete chemical reaction networks
• Algebraic biochemistry: a framework for analog online computation in cells
• The importance of thermodynamics for molecular systems, and the importance of molecular systems for thermodynamics
• Dominance and T-Invariants for Petri Nets and Chemical Reaction Networks
• Autocatalysis in reaction networks
• Minimal output unstable configurations in chemical reaction networks and deciders
• Dominance and deficiency for Petri nets and chemical reaction networks
• On a model of online analog computation in the cell with absolute functional robustness: algebraic characterization, function compiler and error control
• Polynomial time algorithms to determine weakly reversible realizations of chemical reaction networks

This page was built for publication: Deterministic Function Computation with Chemical Reaction Networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5200596)