CAREER: Error-Free, Uniform and Composable Chemical Computation

职业：无差错、统一且可组合的化学计算

• 批准号: 1844976
• 负责人: David Doty
• 金额: $ 50万
• 依托单位: University of California-Davis
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-07-01 至 2024-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1844976&HistoricalAwards=false
• 关键词: CAREER; Error; Free; Uniform; Composable

Computation by electronic computers has revolutionized relatively mundane aspects of life, such as shopping and commuting, by automating tasks that previously required human intervention. Similarly, the programming of chemicals-automating the processing of information embedded in molecules could remake the world: smart molecules controlled by programmable chemical reactions could achieve the same level of precise automated control over the configuration of matter at the molecular level. This may one day revolutionize, for example, therapeutic treatments applied within living cells or nanoscale materials fabricated by self-assembly. This project aims to develop the mathematical foundations of such chemical information processing, bringing the engineering of chemistry-based "software" closer to the reliability of modern electronic computing. Research will be directed toward key challenges that have faced practitioners in the field: namely error-prevention, reusability, and the ability to integrate separately designed chemical systems into a properly functioning whole. Insights gleaned from research in classical computer science will be applied to achieve these goals, but new insights, based on the laws of physics and chemistry, will be required to reason about the uniquely molecular interactions mediating chemical computation. The potential applications in medicine or nano-engineering include identifying and curing diseases, as well as self-assembling devices with nanoscale precision. Together with a tightly integrated educational plan based on training female undergraduate mathematics students in computer science research, and a data-driven approach to develop autograding software for undergraduate CS courses, this project will help train a new and diverse generation of interdisciplinary scientists and programmers, who can innovate robust nanoscale information technologies.This project advances the theoretical foundation for programming chemical algorithms-that is, algorithms executed by artificially synthesized chemical reactions-ensuring they have three crucial properties that are lacking, or at best poorly understood, in existing systems: (1) error-free: implementable by real chemicals that faithfully execute the intended algorithm, (2) uniform: correct for any "population size", i.e., the total number of molecules, unlike many current algorithms where reactions must be tailored specifically to the population size and (3) composable: can be packaged into functional modules that are easily combined. As DNA nanotechnology and molecular computing mature, so too must our insight into their fundamental abilities and limitations. A rigorous theory of chemical computing will guide the experimental breakthroughs of the future. Development of this theory will be guided by a preference for substrate-independence, identifying the laws of computation obeyed by all chemical systems, sifting out artifacts of particular technologies from their shared unifying principles. The development of techniques to make chemical algorithms error-free, uniform, and composable could lead to a systematic path for programming chemistry, making it understandable and usable by non-chemists thus allowing the molecular computing revolution to take flight. Advances in programmable kinetic barriers in implementing an autocatalytic reaction could eventually lead to a significant technological breakthrough allowing error-resilient single-molecule detection.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

电子计算机的计算已经彻底改变了生活中相对平凡的方面，例如购物和通勤，通过自动化以前需要人工干预的任务。类似地，对化学物质进行编程，使分子中嵌入的信息处理自动化，可以重塑世界：由可编程化学反应控制的智能分子可以在分子水平上实现对物质结构的精确自动控制。例如，这可能有一天会彻底改变应用于活细胞或通过自组装制造的纳米级材料的治疗方法。该项目旨在开发这种化学信息处理的数学基础，使基于化学的“软件”工程更接近现代电子计算的可靠性。研究将针对该领域从业者面临的关键挑战：即错误预防，可重复使用性以及将单独设计的化学系统集成为一个正常运行的整体的能力。从经典计算机科学的研究中收集的见解将被应用于实现这些目标，但基于物理和化学定律的新见解将需要推理介导化学计算的独特分子相互作用。在医学或纳米工程方面的潜在应用包括识别和治疗疾病，以及具有纳米级精度的自组装装置。再加上一个紧密结合的教育计划，以培训计算机科学研究中的女本科数学学生为基础，以及一个数据驱动的方法来开发本科计算机科学课程的自动评分软件，这个项目将有助于培养新一代的跨学科科学家和程序员，谁可以创新强大的纳米级信息技术。该项目推进化学算法编程的理论基础-即通过人工合成的化学反应执行的算法--确保它们具有现有系统中缺乏的或者最多是知之甚少的三个关键特性：（1）无差错：可由忠实地执行预期算法的真实的化学物质实现，（2）均匀：对于任何“群体大小”都是正确的，即，分子的总数，不像许多当前的算法，其中反应必须专门针对群体大小和（3）可组合：可以包装成容易组合的功能模块。随着DNA纳米技术和分子计算的成熟，我们也必须深入了解它们的基本能力和局限性。一个严格的化学计算理论将指导未来的实验突破。这一理论的发展将受到对基底独立性的偏好的指导，确定所有化学系统都遵守的计算定律，从它们共享的统一原则中筛选出特定技术的人工制品。使化学算法无错误，统一和可组合的技术的发展可能会导致化学编程的系统路径，使其能够被非化学家理解和使用，从而使分子计算革命起飞。在实现自催化反应的可编程动力学屏障方面取得的进展最终可能导致重大的技术突破，从而实现错误恢复的单分子检测。该奖项反映了NSF的法定使命，并被认为值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估来支持。

项目成果

A time and space optimal stable population protocol solving exact majority

• DOI: 10.1109/focs52979.2021.00104
• 发表时间: 2022-02
• 期刊: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)
• 作者: David Doty;Mahsa Eftekhari;L. Gąsieniec;Eric E. Severson;P. Uznański;Grzegorz Stachowiak

Brief Announcement: A Time and Space Optimal Stable Population Protocol Solving Exact Majority

简短公告：解决绝对多数的时空最优稳定种群协议

• DOI: 10.1145/3465084.3467942
• 发表时间: 2021
• 期刊: Proceedings of the 40th ACM Symposium on Principles of Distributed Computing
• 作者: Doty, David;Eftekhari, Mahsa;Gąsieniec, Leszek;Severson, Eric;Stachowiak, Grzegorz;Uznański, Przemyslaw
• 通讯作者: Uznański, Przemyslaw

A survey of size counting in population protocols

人口方案中规模计数的调查

• DOI: 10.1016/j.tcs.2021.08.038
• 发表时间: 2021
• 期刊: Theoretical Computer Science
• 影响因子: 1.1
• 作者: Doty, David;Eftekhari, Mahsa
• 通讯作者: Eftekhari, Mahsa

Computing Properties of Thermodynamic Binding Networks: An Integer Programming Approach

• DOI: 10.4230/lipics.dna.27.2
• 发表时间: 2020-11
• 作者: David Haley;David Doty

Programming Substrate-Independent Kinetic Barriers With Thermodynamic Binding Networks

• DOI: 10.1109/tcbb.2019.2959310
• 发表时间: 2021-01-01
• 期刊: IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS
• 影响因子: 4.5
• 作者: Breik, Keenan;Chalk, Cameron;Soloveichik, David
• 通讯作者: Soloveichik, David