Chen, Ho-Lin and Doty, David and Soloveichik, David (2014) Rate-Independent Computation in Continuous Chemical Reaction Networks. In: ITCS '14 Proceedings of the 5th conference on Innovations in theoretical computer science. ACM , New York, NY, pp. 313-326. ISBN 978-1-4503-2698-8 http://resolver.caltech.edu/CaltechAUTHORS:20140219-153304453
- Published Version
Restricted to Caltech community only
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20140219-153304453
Understanding the algorithmic behaviors that are in principle realizable in a chemical system is necessary for a rigorous understanding of the design principles of biological regulatory networks. Further, advances in synthetic biology herald the time when we'll be able to rationally engineer complex chemical systems, and when idealized formal models will be- come blueprints for engineering. Coupled chemical interactions in a well-mixed solution are commonly formalized as chemical reaction networks (CRNs). However, despite the widespread use of CRNs in the natural sciences, the range of computational behaviors exhibited by CRNs is not well understood. Here we study the following problem: what functions f : ℝ^k → ℝ can be computed by a chemical reaction network, in which the CRN eventually produces the correct amount of the "output" molecule, no matter the rate at which reactions proceed? This captures a previously unexplored, but very natural class of computations: for example, the reaction X_1 + X_2 → Y can be thought to compute the function y = min(x_1, x_2). Such a CRN is robust in the sense that it is correct whether its evolution is governed by the standard model of mass-action kinetics, alternatives such as Hill-function or Michaelis-Menten kinetics, or other arbitrary models of chemistry that respect the (fundamentally digital) stoichiometric constraints (what are the reactants and products?). We develop a formal definition of such computation using a novel notion of reachability, and prove that a function is computable in this manner if and only if it is continuous piecewise linear.
|Item Type:||Book Section|
|Additional Information:||Copyright is held by the owner/author(s). Publication rights licensed to ACM. We thank Manoj Gopalkrishnan, Elisa Franco, Damien Woods, and the organizers and participants of the American Mathematical Institute workshop on Mathematical Prob- lems Arising from Biochemical Reaction Networks for in- sightful discussions. We are grateful to anonymous reviewers for insightful comments and suggestions that have improved this paper. DD was supported by the Molecular Program- ming Project under NSF grants 0832824 and 1317694 and by NSF grants CCF-1219274 and CCF-1162589. DS was supported by NIGMS Systems Biology Center grant P50 GM081879.|
|Subject Keywords:||Chemical Reaction Networks, Mass-Action, Analog Computation, Piecewise-Linear|
|Classification Code:||F.1 [Theory of Computation]: Computation by Abstract Devices; C.1.3 [Computer systems organization]: Other Architecture Styles|Analog computers|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Kristin Buxton|
|Deposited On:||26 Mar 2014 20:36|
|Last Modified:||26 Mar 2014 20:36|
Repository Staff Only: item control page