Computing properties of stable configurations of thermodynamic binding networks
Computing properties of stable configurations of thermodynamic binding networks
复制标题
DOI：
10.1016/j.tcs.2018.10.027
复制
发表时间：
2019-09-20
影响因子：
1.1
通讯作者：
Soloveichik, David
中科院分区：
文献类型：
--
作者：
Breik, Keenan;Thachuk, Chris;Soloveichik, David
化学计算的前景在于控制与传统电子微控制器不兼容的系统，并应用于合成生物学和纳米级制造。计算通常嵌入动力学中，即化学系统的特定时间演化。然而，如果所需的输出不是热力学稳定的，基本的物理化学决定了热力学力将在整个计算过程中将系统推向错误。引入热力学结合网络（TBN）模型来研究如何使热力学平衡与所需计算相一致，它理想化了构型熵和结合之间的权衡。在这里，我们证明了计算困难的自然问题TBN和开发一个实用的算法，通过将问题转化为命题逻辑和解决由此产生的公式来验证结构的正确性。TBN模型与自动化验证工具一起将有助于为分子计算中的错误减少策略提供信息，包括广泛研究的链置换级联和算法瓦片组装模型。(C)2018 Elsevier B.V.版权所有。
The promise of chemical computation lies in controlling systems incompatible with traditional electronic micro-controllers, with applications in synthetic biology and nano-scale manufacturing. Computation is typically embedded in kinetics the specific time evolution of a chemical system. However, if the desired output is not thermodynamically stable, basic physical chemistry dictates that thermodynamic forces will drive the system toward error throughout the computation. The thermodynamic binding network (TBN) model was introduced to formally study how the thermodynamic equilibrium can be made consistent with the desired computation, and it idealizes tradeoffs between configurational entropy and binding. Here we prove the computational hardness of natural questions about TBNs and develop a practical algorithm for verifying the correctness of constructions by translating the problem into propositional logic and solving the resulting formula. The TBN model together with automated verification tools will help inform strategies for error reduction in molecular computing, including the extensively studied models of strand displacement cascades and algorithmic tile assembly. (C) 2018 Elsevier B.V. All rights reserved.