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

自组装是简单物体在很少的外部控制下相互连接形成复杂结构的过程。鉴于自组装在自然界中非常普遍，几乎可以肯定的是，自组装技术最终将允许精确和高效的纳米结构制造。自我组装有很多种。本项目选择关注算法DNA自组装，旨在从编程（即算法）和数学的角度理解自组装。算法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.