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

近年来，出现了基于DNA的计算，以及生产物体、坚固设备和周期阵列的DNA纳米技术的发展。我们建议将这些领域结合起来，通过使用健壮的二态DNA器件和DNA阵列组装技术来构建一个能够执行简单计算的可编程有限状态机的原型。目标是产生一个可编程、产生输出和可重用的系统。我们利用王片、有限状态机(换能器)和可计算功能之间的联系。主要思想是使用DNA TX分子来表示换能器转换，并使用一系列两态DNA设备来对输入进行编程。一旦输入被编程，换能器的计算仅通过DNA自组装获得。此外，ITER和换能器的组合也是可能的，因此可以获得所有可计算的函数。该项目由两个主要任务组成：1.用输入分子和TX跃迁分子的单个组装输出的有限状态机模拟计算。通过DNA双态器件和TX分子的程序输入获得换能器计算。该项目制作了一种纳米机器的原型，这种机器可能是可编程的，产生的输出可以作为新设备的输入，或者作为用于纳米电子学的纳米结构的组织和生长的模板。所提出的机器具有对这种增长进行算法控制的潜力。从理论上讲，机器的设计和(局部和全球)编码(即纠错)的需要将导致算法图案设计中新技术的发展。基于DNA的计算的研究依赖于许多学科，如计算机科学、DNA化学、核酸酶学、热力学和分子物理。很少有人在充分准备的情况下进入它。在这个项目的过程中，我们将尝试为这个问题提供一些补救措施。参与这项工作的研究生、本科生和高中生将接受独特的培训，并将成为独特的跨学科研究科学家。三名研究生(两名在纽约大学，一名在南佛罗里达大学)将通过这一奖项接受研究生培训。他们将彼此见面，并熟悉对方大学同事的思想和方法。此外，我们将把一名本科生包括在这个项目中，以获得将计算机科学与DNAnanoTechnology相结合的经验。我们的目标是将一名高中生包括在他们有资格从事的部分工作中(例如，不需要使用辐射的计算和实验)。除了他们自己的纳米技术和数学学科，PI和共同PI是基于DNA的计算社区的重要成员。这一共同性的两个方面都认识到它正在与结构DNA纳米技术融合。为认识到这一跨学科现象，国际和平协会和共同国际和平协会参与创建了“国际纳米科学、计算和工程学会”(分别担任会长和财务主管)，目的是促进参与社区成员之间的交流，并通过为年轻成员提供认可和他们的想法的论坛，承认和促进他们的事业。

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.