AF: Small: Theory of Molecular Programming: Computability and Complexity

AF：小：分子编程理论：可计算性和复杂性

• 批准号: 1219274
• 负责人: David Doty
• 金额: $ 42.5万
• 依托单位: California Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-07-01 至 2015-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1219274&HistoricalAwards=false
• 关键词: AF; Small; Theory; Molecular; Programming

The ability of scientists and engineers to organize and control matter at the nanoscale is rapidly improving as ever more complicated molecular systems are being built. It is becoming clear that a systematic approach is needed to guide molecular engineers as to the kinds of systems that are useful to construct and are capable of interesting behavior. Consider the state of computer science in the 1940's, at the dawn of the information revolution. A handful of special-purpose, error-prone computers had been built. Alan Turing and others had just initiated the theoretical study of computability theory, which tells us what computers can do given unlimited resources. It was to be 20 years before the advent of computational complexity theory, the study of what computers can do given limited resources. Researchers find themselves in a similar position today in molecular computing. Experimental work in this area is becoming more and more sophisticated. DNA strand displacement has been used to construct a logic circuit, whose components are free-floating DNA strands and complexes, capable of computing square roots. DNA tile assembly has been used to implement cellular automata capable of growing into fractal patterns and counting in binary. DNA origami is enabling precise control and placement of a variety of molecular structures and systems. The PIs believe that molecular programming will ultimately allow fabrication and control of nanoscale and macroscopic artifacts whose nanoscale parts are arranged with nanoscale precision, that these artifacts will have complexity comparable to that of biological organisms, and that molecular fabrication paradigms will be inspired by biological growth and development.Investigation of precisely what feats are possible and impossible to implement with molecular systems, using rigorous mathematical models, is a primary aim in this proposal. Work will focus on the tradeoffs between various resource bounds that arise uniquely from molecular programming. These include number of distinct molecular species, number of bond types, amount of fuel molecules consumed, and time or volume required for assembly/computation. Molecular resources such as molecular motion, rigidity, randomness and nondeterminism will be studied. Today, a proper understanding of which tasks are efficiently executable by chemistry is totally absent. The major goals of this project are to develop this understanding and provide a theoretical foundation for the systematic development of molecular programming.The project includes funding for summer undergraduate students, and the PIs will act as advisees for senior-year undergraduate projects. Additionally, the PIs will be involved in teaching students that are not traditionally associated with computer science so that future molecular engineers can be exposed to methods and practices needed for designing complex nanoscale chemical systems. Students will learn the theory of molecular programming and be part of a new generation to work in this exciting field. The proposed research will be complemented by educational and outreach activities with underrepresented minorities from local K-12 schools.

随着越来越复杂的分子系统的建立，科学家和工程师在纳米尺度上组织和控制物质的能力正在迅速提高。越来越明显的是，需要一种系统的方法来指导分子工程师构建有用的系统并能够产生有趣的行为。想一想 20 世纪 40 年代信息革命初期的计算机科学状况。一些专用的、容易出错的计算机已经被制造出来。艾伦·图灵和其他人刚刚发起了可计算性理论的理论研究，该理论告诉我们在给定无限资源的情况下计算机可以做什么。 20 年后，计算复杂性理论出现，该理论研究计算机在资源有限的情况下可以做什么。如今，研究人员发现自己在分子计算领域处于类似的境地。这一领域的实验工作正变得越来越复杂。 DNA 链位移已被用来构建逻辑电路，其组件是自由浮动的 DNA 链和复合物，能够计算平方根。 DNA瓦片组装已被用于实现能够生长成分形图案并以二进制计数的细胞自动机。 DNA 折纸能够精确控制和放置各种分子结构和系统。 PI 认为，分子编程最终将允许制造和控制纳米级和宏观工件，其纳米级部件以纳米级精度排列，这些工件将具有与生物有机体相当的复杂性，并且分子制造范例将受到生物生长的启发使用严格的数学模型，准确研究分子系统可能实现和不可能实现的壮举是该提案的主要目标。工作重点是分子编程特有的各种资源界限之间的权衡。这些包括不同分子种类的数量、键类型的数量、消耗的燃料分子的数量以及组装/计算所需的时间或体积。将研究分子运动、刚性、随机性和非确定性等分子资源。如今，完全不了解化学可以有效执行哪些任务。该项目的主要目标是加深这种理解，并为分子编程的系统发展提供理论基础。该项目包括为暑期本科生提供资助，PI 将担任高年级本科生项目的顾问。此外，PI 将参与教授传统上与计算机科学无关的学生，以便未来的分子工程师能够接触到设计复杂纳米级化学系统所需的方法和实践。学生将学习分子编程理论，并成为在这个令人兴奋的领域工作的新一代的一部分。拟议的研究将得到当地 K-12 学校代表性不足的少数群体的教育和外展活动的补充。