https://scholars.lib.ntu.edu.tw/handle/123456789/634627
標題: | Rate-independent Computation in Continuous Chemical Reaction Networks | 作者: | CHEN HO-LIN Doty, David Reeves, Wyatt Soloveichik, David |
關鍵字: | Additional Key Words and PhrasesChemical reaction networks | analog computation | mass-action | piecewise-linear; cs.ET; cs.ET; Quantitative Biology - Molecular Networks | 公開日期: | 23-五月-2023 | 卷: | 70 | 期: | 3 | 來源出版物: | Journal of the ACM | 摘要: | 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 will 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 CRN, 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 X1 + X2 → Y can be thought to compute the function y = min (x1, x2). 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 reachability relation based on a broad notion of "what could happen"if reaction rates can vary arbitrarily over time. Using reachability, we define stable computation analogously to probability 1 computation in distributed computing and connect it with a seemingly stronger notion of rate-independent computation based on convergence in the limit t → ∞ under a wide class of generalized rate laws. Besides the direct mapping of a concentration to a nonnegative analog value, we also consider the "dual-rail representation"that can represent negative values as the difference of two concentrations and allows the composition of CRN modules. We prove that a function is rate-independently computable if and only if it is piecewise linear (with rational coefficients) and continuous (dual-rail representation), or non-negative with discontinuities occurring only when some inputs switch from zero to positive (direct representation). The many contexts where continuous piecewise linear functions are powerful targets for implementation, combined with the systematic construction we develop for computing these functions, demonstrate the potential of rate-independent chemical computation. |
描述: | accepted to JACM (https://doi.org/10.1145/3590776); preliminary version appeared in ITCS 2014: http://doi.org/10.1145/2554797.2554827 |
URI: | https://scholars.lib.ntu.edu.tw/handle/123456789/634627 | ISSN: | 00045411 | DOI: | 10.1145/3590776 |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。