EAGER: Algorithmic DNA Self-Assembly

自组装是一个过程，通过这个过程，简单的对象在最小或没有外部控制的情况下组装成复杂的结构。据信，自组装技术将最终允许精确和高效的纳米结构的制造。自组装在自然界中是常见的，但还没有从数学和编程中很好地理解（即，算法）观点。自我组装有很多种。本项目的重点是DNA分子的自组装。由多条DNA链组成的小分子被设计为DNA自组装的四边构建块（称为瓦片）。实验工作表明，这些构建块可以有效地执行计算以及组装晶体。这种积木的自组装过程的一些关键方面已被用来制定一个初步的数学模型，称为抽象瓦片组装模型。这个模型通过增加一个自然的生长机制扩展了王的二维耕作的数学理论。该模型由一组方形瓷砖组成。瓷砖的四个边都与胶水（以DNA链的形式实现）相关联。图块集中的特殊图块被指定为种子。自组装通过以下方式进行：从种子开始，然后每当瓦片与种子之间的总结合强度不小于阈值时，将瓦片集合中的瓦片的副本逐个附接到生长的种子（其被实施为管中的温度）。智力优点：这个项目是在纳米技术和计算机科学的交叉点，重点是探索DNA自我的潜力和局限性，从算法的角度来看。该项目将建立在PI在这一新兴领域的先前结果和见解的基础上，探索将编码算法编码到DNA瓦片的胶水中以指导自组装过程的理论。具体而言，该项目将研究三个相互关联的研究方向。这些方向一起将探索新的方法，以最大限度地减少用于组装结构的具有不同胶水的瓷砖的数量（这被称为瓷砖复杂度），以最大限度地减少组装结构所需的时间，并在组装过程中以及在组装的结构上施加期望的结构特性。这些方向的一个共同主题是寻求自动设计DNA自组装系统的方法。我们在这个项目中的方法将是理论性的，我们将设计算法并证明这些方向的复杂性界限。更广泛的影响：DNA自组装既是纳米技术的一种形式，也是计算的一种模型。作为一种计算模型，算法DNA自组装首先将用于给定计算问题的计算机程序编码成DNA瓦片的胶水。然后，瓦片彼此结合以执行程序来产生DNA纳米结构，该DNA纳米结构反过来编码计算问题的期望输出。作为一种纳米技术，算法DNA自组装的目标是设计胶水来编程一组瓦片以组装成所需的纳米结构。PI在过去的春季季度（2010年春季）教授了一门新课程，内容是高等本科生和一年级研究生的DNA自组装。PI将在未来几年内继续定期教授这门课程，无论是以讲座为基础的课程还是以研讨会为基础的课程。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.