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

点击翻译按钮获取中文摘要

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.