Nano: Programmable Finite State Machines Achieved by DNA Self-Assembly

Nano：DNA自组装实现的可编程有限状态机

• 批准号: 0432009
• 负责人: Nadrian Seeman
• 金额: $ 30万
• 依托单位: New York University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-09-01 至 2007-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0432009&HistoricalAwards=false
• 关键词: Nano; Programmable; Finite; State; Machines

Recent years have seen the advent of DNA-based computation, as well as the development of aDNA nanotechnology that produces objects, robust devices and periodic arrays. We propose tocombine these areas, by using a robust 2-state DNA device and DNA array assembly techniquesto prototype a programmable finite state machine capable of performing simple computations.The goal is to produce a system that is programmable, produces an output and is reusable.We exploit connections between Wang tiles, finite state machines (transducers) and com-putable functions. The main idea uses DNA TX molecules to represent transducer transitionsand a sequence of 2-state DNA devices to program the input. Once the input is programmed,the computation of the transducer is obtained solely by DNA self-assembly. Further more, iter-ations and composition of transducers is also possible and hence all computable functions canbe obtained.The project is composed of two major tasks,1. To simulate computation by a finite state machine with output by a single assembly ofinput molecules and TX transition molecules.2. To obtain transducer computation with a programmale input by DNA 2-state devices andTX molecules.Intelectual Merit. The project prototypes a nanomachine that is potentially programmableand produces an output that can serve as an input in a new device or as a template for orga-nization and growth of nanostructures used in nanoelectronics. The proposed machine has apotential for an algorithmic control of this growth. Theoretically, the design of the machine andthe need for encoding (locally and globally) that is error correcting will lead to development ofnew techniques in algorithmic pattern design.Broader Impact. Research in DNA-based computation relies on many disciplines, such ascomputer science, DNA chemistry, nucleic acid enzymology, thermodynamics and molecularphysics. Few individuals enter in to it with adequate preparation. We will attempt to providesome remedy for this problem during the course of this project. The graduate, undergraduateand high school students who participate in this work will be uniquely trained and will beprepared as unique interdisciplinary research scientists. Three graduate students (two at NewYork University and one at the University of South Florida) will receive graduate trainingthrough this award. They will meet with each other, and become familiar with the thinking andmethodologies of their opposite colleagues in the other university. In addition, we will includean undergraduate in the project, to gain experience in combining computer science with DNAnanotechnology. We aim to include a high school student in the parts of the work for whichthey are eligible (e.g., computation and experiments not entailing the use of radiation).Besides their own nanotechnological and mathematical disciplines, the PI and the co-PI areprominent members of the DNA-based computation community. Both facets of this commu-nity recognize that it is converging with structural DNA nanotechnology. In recognition ofthis interdisciplinary phenomenon, the PI and the co-PI are involved in founding (as presidentand treasurer, respectively) the \International Society for Nanoscale Science, Computation andEngineering" with a goal to facilitate communication among the members of the participatingcommunities, and to recognize and promote the careers of the younger members, by offeringthem recognition and a forum for their ideas.

近年来，基于DNA的计算出现了，以及DNA纳米技术的发展，产生了物体，坚固的设备和周期性阵列。我们建议结合这些领域，通过使用一个强大的2状态DNA设备和DNA阵列组装技术，原型的可编程有限状态机能够执行简单的计算。我们的目标是产生一个系统，可编程的，产生的输出和可重复使用。我们利用王瓦片，有限状态机（传感器）和可计算的功能之间的连接。其主要思想是使用DNA TX分子来表示换能器转换，并使用一系列双态DNA器件来编程输入。一旦输入被编程，传感器的计算仅通过DNA自组装获得。此外，还可以进行迭代和组合，从而得到所有可计算的函数。用输入分子和TX跃迁分子的单一组合来模拟有限状态机的计算.利用DNA二态器件和TX分子的程序输入实现传感器计算.该项目的原型是一个nanomachine，这是潜在的可编程和生产的输出，可以作为一个新的设备或作为一个模板，在纳米电子学中使用的纳米结构的有机化和增长的输入。拟议的机器有潜力的算法控制这种增长。从理论上讲，机器的设计和对纠错编码（局部和全局）的需求将导致算法模式设计中新技术的发展。DNA计算的研究涉及到计算机科学、DNA化学、核酸酶学、热力学和分子物理学等多个学科。很少有人在做好充分准备的情况下进入它。在这个项目的实施过程中，我们将设法为这个问题提供一些补救办法。参与这项工作的研究生、本科生和高中生将受到独特的培训，并将成为独特的跨学科研究科学家。三名研究生（两名在纽约大学，一名在南佛罗里达大学）将通过该奖项接受研究生培训。他们将相互见面，熟悉对方大学的同行的思维和方法。此外，我们将包括一名本科生在该项目中，以获得经验，结合计算机科学与DNA纳米技术。我们的目标是让高中生参与他们有资格参与的工作（例如，除了他们自己的纳米技术和数学学科，PI和co-PI是基于DNA的计算社区的杰出成员。这一共同体的两个方面都认识到它正在与结构DNA纳米技术融合。认识到这一跨学科现象，PI和co-PI参与创立（分别担任主席和财务主管）“国际纳米科学，计算和工程学会”，其目标是促进参与社区成员之间的沟通，并通过为他们提供认可和论坛来认可和促进年轻成员的职业生涯。