权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

AF：小：DNA 自组装的组合算法和计算复杂性

基本信息

批准号：
1217770
负责人：
Ming-Yang Kao
金额：
$ 40万
依托单位：
Northwestern University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2012
资助国家：
美国
起止时间：
2012-08-01 至 2016-07-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1217770&HistoricalAwards=false
关键词：
AF Small Combinatorial Algorithms Computational

项目摘要

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.

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