EAGER: Algorithmic DNA Self-Assembly

Northwestern University, Evanston IL

Investigators

Abstract

Project Summary Self-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.