CAREER: Robust Molecular Computation: Error-Correcting Reaction Networks and Leakless DNA Circuits

计算机科学和电子工程已经掌握了电子计算，但有一个重要的计算领域仍然知之甚少：化学信息处理。化学反应引起的计算在生物学中很普遍-例如，我们体内的每个细胞都必须对内部和外部化学信号进行复杂的信息处理。类似地，重要的是要学会如何合理地设计能够决策的生化途径。与硅芯片不同，分子计算机可以在细胞内运行并控制它们的活动。可编程化学反应可用于制造、化学传感和医学等一系列应用。例如，将药物活性靶向疾病细胞并响应特定分子线索而激活的“智能药物”将具有最小的副作用并改善治疗结果。该提案解决了化学信息处理中的一个关键算法挑战：如何在化学环境的无序和易出错的性质下稳健地计算。数学模型（化学反应网络）提供了清晰的思路，以阐明校对化学算法的普遍原则，而实验室实现（使用工程DNA分子）提供了必要的基础。这一建议的成功不仅将导致新的理论理解，但新一代的功能分子器件。具体而言，该提案将解决医学诊断领域的一个长期挑战：DNA的无酶序列特异性检测。无酶系统有可能适用于“现场”操作，因为在现场无法获得先进的实验室设备。拟议的研究方案与教育和外联活动紧密结合。该提案将资助大学课程和教学材料的开发，这些课程和教学材料将培养学生将计算机科学和电气工程的成熟原理应用于分子计算的新领域。主要的教育目标是鼓励下一代科学家突破传统的学科障碍，创造明天的科学和工程领域。此外，该项目将通过游戏化为早期STEM教育做出贡献。拟议的工作使用化学反应网络的形式化模型，严格探索稳健化学计算的原理。化学反应网络形式化了分子在遵循化学动力学的混合溶液中相互作用的计算结果。所描述的工作可以产生化学算法，随着更多的分子参与计算，以及快速和完全无误差的简单函数的计算，误差呈指数级下降。此外，获得的不可能结果，例如计算能力和鲁棒性之间的基本权衡，将有助于避免追求站不住脚的目标。作为对推导化学动力学计算能力的一般定律的补充，该提案的另一个重点是解决DNA纳米技术（链置换反应）中常用分子基元的泄漏（假反应）问题。泄漏使得难以区分阳性信号和背景，这导致灵敏度降低，以及显著降低的计算速度。该提案概述了第一个原则性的方法，以校对链位移系统，可以实现任意低水平的泄漏。

Computer science and electrical engineering have mastered electronic computation, yet there is an important domain of computation that remains poorly understood: chemical information processing. Computation due to chemical reactions is prevalent in biology - for example, every cell in our body must perform sophisticated information processing on internal and external chemical signals. Analogously, it is important to learn how to rationally engineer biochemical pathways that are capable of decision-making. Unlike silicon chips, molecular computers could operate inside cells and control their activity. Programmable chemical reactions could be useful for a range of applications in manufacturing, chemical sensing, and medicine. For example, "smart drugs" that target drug activity to disease cells and activate in response to specific molecular clues would have minimal side effects and improve therapeutic outcomes. This proposal addresses a key algorithmic challenge in chemical information processing: how to compute robustly despite the disordered and error-prone nature of the chemical environment. Mathematical models (chemical reaction networks) provide the clarity of thought to explicate universal principles of proofreading chemical algorithms, while a laboratory realization (using engineered DNA molecules) provides the necessary grounding. The success of this proposal will lead not only to new theoretical understanding but to a new generation of functional molecular devices. Specifically, this proposal will address a long-standing challenge in medical diagnostics: enzyme-free sequence-specific detection of DNA. Enzyme-free systems have the potential to be adapted to "in-the-field" operation, where sophisticated laboratory equipment is out of reach. The research program proposed is tightly coupled to educational and outreach activities. This proposal will fund the development of college courses and instructional material, which will train students in applying the proven principles of computer science and electrical engineering to the new domain of molecular computation. The primary educational goal is to encourage the next generation of scientists to break through traditional disciplinary barriers and create the scientific and engineering fields of tomorrow. Further, the project will contribute to early STEM education through gamification.The proposed work uses the formal model of chemical reaction networks to rigorously explore the principles of robust chemical computation. Chemical reaction networks formalize the computation that results from molecules interacting in a well-mixed solution obeying chemical kinetics. The work described could yield chemical algorithms for decreasing error exponentially as more molecules are involved in the computation, as well as for fast and entirely error-free computation of simple functions. Additionally, the impossibility results obtained, such as the fundamental tradeoffs between computational power and robustness, will help avoid pursuing untenable goals. Complementary to deriving general laws for the computational power of chemical kinetics, another thrust of this proposal addresses the problem of leak (spurious reactions) for a commonly used molecular primitive from DNA nanotechnology (strand displacement reactions). Leak makes it difficult to distinguish positive signal and background, which results in reduced sensitivity, as well as significantly decreased computation speed. This proposal outlines the first principled approach to proofreading in strand displacement systems that could achieve arbitrarily low levels of leak.