Rate-independent Computation in Continuous Chemical Reaction Networks
Rate-independent Computation in Continuous Chemical Reaction Networks
复制标题
DOI：
10.1145/3590776
复制
发表时间：
2023-06-01
影响因子：
2.5
通讯作者：
Soloveichik，David
中科院分区：
文献类型：
--
作者：
Chen，Ho-Lin;Doty，David;Soloveichik，David
理解在化学系统中原则上可实现的算法行为对于严格理解生物调控网络的设计原则是必要的。此外，合成生物学的进步预示着我们将能够合理地设计复杂的化学系统，理想化的正式模型将成为工程的蓝图。在混合良好的溶液中，耦合的化学相互作用通常形式化为化学反应网络（crn）。然而，尽管crn在自然科学中广泛使用，但crn所表现出的计算行为的范围尚未得到很好的理解。在这里，我们研究了以下问题：什么函数f:∈k→∈可以由CRN计算，其中CRN最终产生正确数量的“输出”分子，无论反应进行的速度如何？这捕获了以前未探索但非常自然的一类计算：例如，反应x1 + X2→y可以被认为是计算函数= min （x1, X2）。这样的CRN在某种意义上是可靠的，它是正确的，无论它的进化是由质量作用动力学的标准模型，希尔函数或Michaelis-Menten动力学等替代品，还是其他尊重（基本上是数字的）化学计量学约束（什么是反应物和产物？）的任意化学模型控制的。如果反应速率随时间任意变化，我们基于“可能发生的事情”这一广义概念开发了可达性关系。利用可达性，我们将可定义计算类比于分布式计算中的概率1计算，并将其与广义速率定律下基于极限→∞收敛的看似更强的速率无关计算概念联系起来。除了将浓度直接映射到非负模拟值之外，我们还考虑了“双轨表示”，它可以将负值表示为两个浓度的差值，并允许组成CRN模块。我们证明了一个函数是速率独立可计算的，当且仅当它是分段线性（具有有理系数）和连续（双轨道表示），或者非负的，只有当一些输入从零切换到正（直接表示）时才发生不连续。在许多情况下，连续分段线性函数是实现的强大目标，结合我们为计算这些函数而开发的系统结构，展示了速率无关化学计算的潜力。
Understanding the algorithmic behaviors that arein principlerealizable 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 functionsf : ℝ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 reactionX1+ X2→ Ycan be thought to compute the functiony= 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 definestable computationanalogously to probability 1 computation in distributed computing and connect it with a seemingly stronger notion of rate-independent computation based on convergence in the limitt→ ∞ 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.