AF: Small: Combinatorial Algorithms and Computational Complexity for DNA Self-Assembly

自组装是一个过程，通过这个过程，简单的物体相互连接，在很少的外部控制下形成复杂的结构。鉴于自组装在自然界中非常常见，几乎可以肯定的是，自组装技术最终将允许精确和高效地制造纳米结构。自组装有很多种。算法DNA自组装利用了DNA的四个碱基(即A、C、G、T)可以用来编码信息，而A与T结合、C与G结合的事实被设计成由多条DNA链(即双链以上)组成的小分子作为算法DNA自组装的四边积木(称为瓦片)。实验工作证明，这些积木既可以有效地进行计算，也可以组装晶体。这种积木的自组装过程的一些关键方面已经被用来形成称为抽象瓷砖组装模型的基本数学模型。该模型扩展了二维耕作的数学理论，增加了一种自然机制来生长由瓷砖形成的结构。该模型由一组正方形瓷砖组成。瓷砖的四个面都与一种胶水(以DNA链的形式实现)相关联。瓦片集中的特殊瓦片被指定为初始种子结构。自组装从初始种子结构开始，然后每当瓷砖与种子结构之间的总胶合强度不低于阈值(实现为试管中的温度)时，将瓷砖的副本从瓷砖集合逐一粘到不断生长的种子结构上。在抽象的瓷砖组装模型下，算法DNA自组装既是纳米技术的一种形式，也是一种计算模型。作为一种计算模型，算法DNA自组装首先将计算机程序和给定计算问题的输入数据集编码到DNA瓷砖的胶水中。然后，这些瓷砖通过DNA互补相互绑定，在输入数据集上执行程序，以产生DNA纳米结构，然后对计算问题的期望输出进行编码。作为一种纳米技术，算法DNA自组装的目标是设计胶水，对一组瓷砖进行编程，以组装成所需的纳米结构。该项目将研究算法DNA自组装中相互关联的研究方向，以探索新的方法(1)将用于组装结构的胶水和瓷砖的制造成本降至最低，(2)将组装结构所需的时间以及组装结构中的缺陷量降至最低，以及(3)对组装过程以及组装结构施加所需的结构特性。这些方向的一个共同主题是使DNA自组装系统的设计自动化。该项目将继续首席调查员(PI)的努力，通过阐述理论计算机科学界感兴趣的研究问题，向理论计算机科学界介绍这一新兴的跨学科领域。通过这一项目，国际和平研究所将继续招募任职人数不足的群体成员进入这一领域，特别是计算机科学领域。在过去的两年里，PI在这一领域引入并教授了一门高级本科生和一年级研究生的课程。这门课程吸引了两名来自计算机科学以外的本科生决定申请该领域的博士项目，以及一名化学博士后与PI和本科生暑期研究学生合作。通过这个项目，PI将继续定期教授这门课程，以吸引学生和研究人员进入这个新兴的跨学科计算机科学领域。

Self-assembly is a process by which simple objects connect with each other to form complex structures under very little external control. Given that self-assembly is very common in nature, it is almost certain that self-assembly technologies will ultimately permit precise and efficient fabrications of nanostructures. There are many kinds of self-assembly. This project chooses to focus on algorithmic DNA self-assembly with the goal of understanding self-assembly in general from programming (i.e., algorithmic) and mathematical perspectives.Algorithmic DNA self-assembly takes advantage of the facts that the four bases of DNA (i.e., A, C, G, T) can be used to encode information and that A binds with T and C binds with G. Small molecules consisting of multiple DNA strands (i.e., more than double strands) have been designed to act as four-sided building blocks (which are called tiles) for algorithmic 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 already been used to formulate a fundamental mathematical model called the abstract tile assembly model. This model extends a mathematical theory of two-dimensional tilling by adding a natural mechanism to grow a structure formed by tiles. 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 initial seed structure. Self-assembly proceeds by starting with the initial seed structure and then gluing copies of tiles from the tile set one by one to the growing seed structure whenever the total glue binding strength between a tile and the seed structure is no less than a threshold (which is implemented as the temperature in the tube).Under the abstract tile assembly model, 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 and an input data set for a given computational problem into the glues of DNA tiles. The tiles then bind with each other through DNA complementarity to execute the program on the input data set 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 project will investigate interconnected research directions in algorithmic DNA self-assembly to explore new ways (1) to minimize the cost of manufacturing the glues and tiles used to assemble a structure, (2) to minimize the amount of time needed to assemble a structure as well as the amount of defects in the assembled structure, and (3) to impose desirable structural properties on the assembly process as well as on the assembled structure. A common theme across these directions is to automate the design of DNA self-assembly systems. The project will continue the efforts of the Principle Investigator (PI) to introduce this emerging interdisciplinary field to the theoretical computer science community by formulating research problems of interest to that community. With this project, the PI will continue to recruit members of under-represented groups into this field in particular and into computer science in general. The PI has introduced and taught a course in this field in the past two years at the level of advanced undergraduate students and first-year graduate students. This course attracted two undergraduate students from outside computer science to decide to apply to PhD programs in this field and a postdoctoral fellow in Chemistry to collaborate with the PI and undergraduate summer research students. With this project, the PI will continue to teach this course on a regular basis to attract students and researchers into this emerging interdisciplinary computer science field.