MIT Department of Electrical Engineering & Computer Science

Algorithmic Self-Assembly of DNA: Theory and Experiment

Erik Winfree
Caltech

Monday, April 6, 1998
4:00 PM (refreshments 3:45)
Room NE43-518
EECS Special Seminar

Abstract

Biology makes things far smaller and more complex than anything produced by human engineering. The challenge of engineering molecular systems as complex as a simple bacterium remains daunting if not impossible. However, the biotechnology revolution has for the first time given us the tools necessary to consider engineering on the molecular level. Len Adleman's recent experimental demonstration of a DNA computation has shown how logical information can be mapped into DNA and manipulated by standard laboratory techniques, opening the door for further study of "programmable" biochemical reactions. My research has focussed on understanding the computational properties of a single mechanism, the self-assembly of DNA by hybridization. New models of computation are developed that illuminate a close theoretical relation of DNA self-assembly to the Chomsky hierarchy of formal languages. This theory combines the purely mathematical Tiling Problem, proposed in 1961 by Hao Wang, with the branched DNA constructions of Nadrian Seeman, making theoretical use of self-assembled and algorithmically patterned two-dimensional lattices of DNA. The self-assembly process can be designed to simulate the activity of any one-dimensional cellular automaton, thereby achieving a "one pot" chemical computer capable of universal computation. Encouraged by these results, I have begun an experimental investigation of algorithmic self-assembly using DNA. A competition experiment suggests that an individual logical step can proceed correctly by self-assembly, while a companion experiment suggests that two-dimensional lattices of DNA can be programmed to self-assemble and can be visualized by atomic force microscopy. We have reason to hope, therefore, that DNA structures can be designed to self-assemble according to programmable rules. This system represents a first step toward the ability to "program" material at the molecular level.