EAGER: Algorithmic DNA Self-Assembly

项目摘要自组装是简单对象在最小或没有外部控制的情况下组装成复杂结构的过程。人们相信，自组装技术最终将使纳米结构的精确和高效制造成为可能。自组装在自然界中很常见，但从数学和编程(即算法)的角度来看，人们还没有很好地理解它。自组装有很多种。这个项目的重点是DNA分子的自组装。由多条DNA链组成的小分子被设计成DNA自组装的四边积木(称为瓷砖)。实验工作证明，这些积木既可以有效地进行计算，也可以组装晶体。这种积木的自组装过程的一些关键方面已被用来形成称为抽象瓷砖组装模型的初步数学模型。这个模型通过增加自然的生长机制，扩展了王的二维耕作的数学理论。该模型由一组正方形瓷砖组成。瓷砖的四个面都与一种胶水(以DNA链的形式实现)相关联。瓦片组中的特殊瓦片被指定为种子。自组装是从种子开始，然后每当瓷砖与种子之间的总结合强度不低于阈值(实现为试管中的温度)时，将瓷砖的副本从瓷砖集合逐一贴到不断生长的种子上。智能优点：该项目是纳米技术和计算机科学的交叉，重点是从算法的角度探索DNA自组装的潜力和局限性。该项目将建立在PI在这个新兴领域的先前结果和见解的基础上，探索将算法编码到DNA瓷砖胶水中的理论，以指导自组装过程。具体地说，该项目将调查三个相互关联的研究方向。这些方向将共同探索新的方法，以最小化用于组装结构的具有不同胶水的瓷砖的数量(称为瓷砖复杂性)，最小化组装结构所需的时间量，并将所需的结构特性强加于组装过程以及组装的结构上。这些方向的一个共同主题是寻找自动化DNA自组装系统设计的方法。我们在这个项目中的方法将是理论上的，我们将设计算法并证明这些方向的复杂性界限。更广泛的影响：算法DNA自组装既是纳米技术的一种形式，也是一种计算模型。作为一种计算模型，算法DNA自组装首先将给定计算问题的计算机程序编码到DNA瓷砖的胶水中。然后，这些瓷砖相互绑定，执行程序以产生DNA纳米结构，该纳米结构反过来编码计算问题的期望输出。作为一种纳米技术，算法DNA自组装的目标是设计胶水，对一组瓷砖进行编程，以组装成所需的纳米结构。在过去的春季季度(2010年春季)，PI教授了一门关于算法DNA自组装的新课程，在高级本科生和一年级研究生的水平上。在接下来的几年里，国际和平协会将继续定期教授这门课程，无论是以讲座为基础的课程，还是以研讨会为基础的课程。PI将从这个项目中获得的结果将被纳入课程。这门课程向学生介绍算法和纳米技术交叉领域的研究机会，更广泛地使用类似科幻小说的DNA自组装研究来促进学生的多学科研究和思考。关键词：DNA自组装；算法；复杂性理论；计算模型；自然启发计算；纳米技术。

Project SummarySelf-assembly is a process by which simple objects assemble into complex structures under minimal or no external control. It is believed that self-assembly technology will ultimately permit precise and efficient fabrications of nanostructures. Self-assembly is common in nature but is not yet well understood from mathematical and programming (i.e., algorithmic) perspectives. There are many kinds of self-assembly. This project will focus on self-assembly of DNA molecules.Small molecules consisting of multiple DNA strands have been designed to act as four-sided building blocks (which are called tiles) for DNA self-assembly. Experimental work has demonstrated that these building blocks can effectively perform computation as well as assemble crystals. Some key aspects of the self-assembly process of such building blocks have been used to formulate a preliminary mathematical model called the abstract tile assembly model. This model extends Wang's mathematical theory of two-dimensional tilling by adding a natural mechanism for growth. The model consists of a set of square tiles. The four sides of a tile are each associated with a glue (which is implemented as a DNA strand). A special tile in the tile set is designated as the seed. Self-assembly proceeds by starting with the seed and then attaching copies of tiles from the tile set one by one to the growing seed whenever the total binding strength between a tile and the seed is no less than a threshold (which is implemented as the temperature in the tube).Intellectual Merit: This project is in the intersection of nanotechnology and computer science with a focus on exploring the potential and limitation of DNA self-assembly from the perspective of algorithms. The project will build on the PI's prior results and insights in this emerging field to explore theories of encoding algorithms into the glues of DNA tiles to guide the self-assembly process. Specifically, the project will investigate three interconnected research directions. These directions together will explore new ways to minimize the number of tiles with distinct glues (which is called the tile complexity) used to assemble a structure, to minimize the amount of time needed to assemble a structure, and to impose desirable structural properties on the assembly process as well as on the assembled structures. A common theme across these directions is to seek ways to automate the design of DNA self-assembly systems. Our approaches in this project will be theoretical, and we will design algorithms and prove complexity bounds for these directions. Broader Impacts: Algorithmic DNA self-assembly is both a form of nanotechnology and a model of computation. As a computational model, algorithmic DNA self-assembly first encodes a computer program for a given computational problem into the glues of DNA tiles. The tiles then bind with each other to execute the program to produce a DNA nanostructure, which in turn encodes the desired output of the computational problem. As a nanotechnology, the goal of algorithmic DNA self-assembly is to design glues to program a set of tiles to assemble into the desired nanostructure. The PI has taught a new course this past spring quarter (spring 2010) on Algorithmic DNA Self-Assembly at the level of advanced undergraduate students and first-year graduate students. The PI will continue to teach this course on a regular basis in the next few years either as a lecture-based course or as a seminar-based course. The results which the PI will obtain from this project will be incorporated into the course. This course introduces students to research opportunities in the intersection of algorithms and nanotechnology and more generally uses science-fiction-like research in DNA self-assembly to promote multidisciplinary research and thinking by students.Key Words: DNA self-assembly; algorithms; complexity theory; models of computation; nature-inspired computing; nanotechnology.