research-article

Rate-independent computation in continuous chemical reaction networks

Authors:

David SoloveichikAuthors Info & Claims

ITCS '14: Proceedings of the 5th conference on Innovations in theoretical computer science

Pages 313 - 326

https://doi.org/10.1145/2554797.2554827

Published: 12 January 2014 Publication History

Abstract

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 become 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₁ + X₂ → Y can be thought to compute the function y = min(x₁, x₂). 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.

References

[1]

U. Alon. Introduction to Systems Biology: Design Principles of Biological Circuits. CRC press, 2006.

[2]

D. Angeli, P. De Leenheer, and E. D. Sontag. On the structural monotonicity of chemical reaction networks. In 45th IEEE Conference on Decision and Control, pages 7--12. IEEE, 2006.

[3]

D. Angeli, P. De Leenheer, and E. D. Sontag. A Petri net approach to the study of persistence in chemical reaction networks. Mathematical Biosciences, 210(2):598--618, 2007.

[4]

D. Angluin, J. Aspnes, and D. Eisenstat. Stably computable predicates are semilinear. In PODC 2006: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, pages 292--299, New York, NY, USA, 2006. ACM Press.

Digital Library

[5]

N. Barkai and S. Leibler. Robustness in simple biochemical networks. Nature, 387(6636):913--917, 1997.

[6]

O. Bournez, P. Chassaing, J. Cohen, L. Gerin, and X. Koegler. On the convergence of population protocols when population goes to infinity. Applied Mathematics and Computation, 215(4):1340--1350, 2009.

Digital Library

[7]

L. Cardelli. Strand algebras for DNA computing. Natural Computing, 10(1):407--428, 2011.

Digital Library

[8]

L. Cardelli and A. Csikász-Nagy. The cell cycle switch computes approximate majority. Scientific Reports, 2, 2012.

[9]

H.-L. Chen, D. Doty, and D. Soloveichik. Deterministic function computation with chemical reaction networks. Natural Computing, 2013. to appear. Preliminary version appeared in DNA 2012.

[10]

Y.-J. Chen, N. Dalchau, N. Srinivas, A. Phillips, L. Cardelli, D. Soloveichik, and G. Seelig. Programmable chemical controllers made from DNA. Nature Nanotechnology, 8(10):755--762, 2013.

[11]

D. T. Gillespie. Exact stochastic simulation of coupled chemical reactions. Journal of Physical Chemistry, 81(25):2340--2361, 1977.

[12]

M. Gopalkrishnan, E. Miller, and A. Shiu. A projection argument for differential inclusions, with applications to persistence of mass-action kinetics. Symmetry, Integrability and Geometry: Methods and Applications, 9(0):25--25, 2013.

[13]

H. K. Khalil. Nonlinear systems. Prentice Hall, 2002.

[14]

T. G. Kurtz. The relationship between stochastic and deterministic models for chemical reactions. The Journal of Chemical Physics, 57(7):2976--2978, 1972.

[15]

S. Ovchinnikov. Max-min representation of piecewise linear functions. Contributions to Algebra and Geometry, 43(1):297--302, 2002.

[16]

L. Qian and E. Winfree. Scaling up digital circuit computation with DNA strand displacement cascades. Science, 332(6034):1196, 2011.

[17]

M. S. Samoilov and A. P. Arkin. Deviant effects in molecular reaction pathways. Nature biotechnology, 24(10):1235--1240, 2006.

[18]

G. Seelig, D. Soloveichik, D. Y. Zhang, and E. Winfree. Enzyme-free nucleic acid logic circuits. Science, 314(5805):1585--1588, 2006.

[19]

D. Soloveichik, M. Cook, E. Winfree, and J. Bruck. Computation with finite stochastic chemical reaction networks. Natural Computing, 7(4):615--633, 2008.

Digital Library

[20]

D. Soloveichik, G. Seelig, and E. Winfree. DNA as a universal substrate for chemical kinetics. Proceedings of the National Academy of Sciences, 107(12):5393, 2010. Preliminary version appeared in DNA 2008.

Cited By

Chen HDoty DReeves WSoloveichik D(2023)Rate-independent Computation in Continuous Chemical Reaction NetworksJournal of the ACM10.1145/359077670:3(1-61)Online publication date: 23-May-2023
https://dl.acm.org/doi/10.1145/3590776
Wathieu LSmith GCeze LThachuk C(2023)Fridge Compiler: Optimal Circuits from Molecular InventoriesComputational Methods in Systems Biology10.1007/978-3-031-42697-1_16(236-252)Online publication date: 9-Sep-2023
https://doi.org/10.1007/978-3-031-42697-1_16
Vasić MChalk CLuchsinger AKhurshid SSoloveichik D(2022)Programming and training rate-independent chemical reaction networksProceedings of the National Academy of Sciences10.1073/pnas.2111552119119:24Online publication date: 9-Jun-2022
https://doi.org/10.1073/pnas.2111552119
Show More Cited By

Index Terms

Rate-independent computation in continuous chemical reaction networks
1. Computer systems organization
  1. Architectures
    1. Other architectures
      1. Analog computers
2. Theory of computation
  1. Models of computation
    1. Abstract machines

Recommendations

Rate-independent Computation in Continuous Chemical Reaction Networks
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 ...
Rate-Independent Continuous Inhibitory Chemical Reaction Networks Are Turing-Universal
Unconventional Computation and Natural Computation
Abstract
We study the model of continuous chemical reaction networks (CRNs), consisting of reactions such as $A + B \to C + D$ that can transform some continuous, nonnegative real-valued quantity (called a concentration) of chemical species A and B into equal ... $\overset{\begin{matrix} \end{matrix}}{}$
$_{}_{}$ $_{}_{}_{}_{}$ $^{}$
Real-time computability of real numbers by chemical reaction networks

We explore the class of real numbers that are computed in real time by deterministic chemical reaction networks that are integral in the sense that all their reaction rate constants are positive integers. We say that such a reaction network computes a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ITCS '14: Proceedings of the 5th conference on Innovations in theoretical computer science

January 2014

566 pages

ISBN:9781450326988

DOI:10.1145/2554797

Program Chair:
Moni Naor
Weizmann Institute of Science

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 January 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ITCS'14

Sponsor:

SIGACT

ITCS'14: Innovations in Theoretical Computer Science

January 12 - 14, 2014

New Jersey, Princeton, USA

Acceptance Rates

ITCS '14 Paper Acceptance Rate 48 of 116 submissions, 41%;

Overall Acceptance Rate 172 of 513 submissions, 34%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

32
Total Citations
View Citations
223
Total Downloads

Downloads (Last 12 months)22
Downloads (Last 6 weeks)1

Reflects downloads up to 13 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Chen HDoty DReeves WSoloveichik D(2023)Rate-independent Computation in Continuous Chemical Reaction NetworksJournal of the ACM10.1145/359077670:3(1-61)Online publication date: 23-May-2023
https://dl.acm.org/doi/10.1145/3590776
Wathieu LSmith GCeze LThachuk C(2023)Fridge Compiler: Optimal Circuits from Molecular InventoriesComputational Methods in Systems Biology10.1007/978-3-031-42697-1_16(236-252)Online publication date: 9-Sep-2023
https://doi.org/10.1007/978-3-031-42697-1_16
Vasić MChalk CLuchsinger AKhurshid SSoloveichik D(2022)Programming and training rate-independent chemical reaction networksProceedings of the National Academy of Sciences10.1073/pnas.2111552119119:24Online publication date: 9-Jun-2022
https://doi.org/10.1073/pnas.2111552119
Chan CShih CChen H(2022)On the Computational Power of Phosphate Transfer Reaction NetworksNew Generation Computing10.1007/s00354-022-00154-640:2(603-621)Online publication date: 27-Mar-2022
https://dl.acm.org/doi/10.1007/s00354-022-00154-6
Chalk CKornerup NReeves WSoloveichik D(2021)Composable Rate-Independent Computation in Continuous Chemical Reaction NetworksIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2019.295283618:1(250-260)Online publication date: 1-Jan-2021
https://doi.org/10.1109/TCBB.2019.2952836
Rodriguez KSarraf NQian L(2021)A Loser-Take-All DNA CircuitACS Synthetic Biology10.1021/acssynbio.1c0031810:11(2878-2885)Online publication date: 8-Oct-2021
https://doi.org/10.1021/acssynbio.1c00318
Zhang C(2021) DNA Computing and Circuits DNA‐ and RNA‐Based Computing Systems10.1002/9783527825424.ch3(31-43)Online publication date: 15-Jan-2021
https://doi.org/10.1002/9783527825424.ch3
Vasic MChalk CKhurshid SSoloveichik DDaumé HSingh A(2020)Deep molecular programmingProceedings of the 37th International Conference on Machine Learning10.5555/3524938.3525837(9701-9711)Online publication date: 13-Jul-2020
https://dl.acm.org/doi/10.5555/3524938.3525837
Degrand ÉFages FSoliman S(2020)Graphical Conditions for Rate Independence in Chemical Reaction NetworksComputational Methods in Systems Biology10.1007/978-3-030-60327-4_4(61-78)Online publication date: 29-Sep-2020
https://doi.org/10.1007/978-3-030-60327-4_4
Paulino NFoo MKim JBates D(2019)Robustness analysis of a nucleic acid controller for a dynamic biomolecular process using the structured singular valueJournal of Process Control10.1016/j.jprocont.2019.02.00978(34-44)Online publication date: Jun-2019
https://doi.org/10.1016/j.jprocont.2019.02.009
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten