COLLOQUIUM
Department of Computer Science and Engineering
University of South Carolina
 
Computational Aspects of Nanoscale Self-Assembly


Jack H. Lutz
Department of Computer Science
Iowa State University

Date: February 10, 2009
Time: 1530-1700 (3:30pm-5pm)
Place: Swearingen 1A03 (Faculty Lounge)

Abstract

DNA tile self-assembly, pioneered by Seeman in the 1980s, is a
promising approach to engineering structures that autonomously
assemble themselves from molecular components. These structures, which
may be complex and aperiodic, can be programmed, in the sense that
they are determined by a designer's selection of the finite set of
molecular component (DNA tile) types from which the structures self-
assemble.

The Tile Assembly Model, introduced by Winfree in the late 1990s, is a
mathematical model of DNA tile self-assembly. Winfree showed that
discrete Sierpinski triangles can self- assemble in the Tile Assembly
Model, and a striking molecular realization of this self-assembly,
using DNA tiles a few nanometers long and verifying the results by
atomic- force microscopy, was achieved by Rothemund, Papadakis, and
Winfree in 2004. Winfree also proved that any computer program (Turing
machine) can be translated into a finite set of tile types whose
self-assembly executes that program. The collection of structures that
can be programmed to self-assemble is thus very rich.

In this talk I will survey these developments, along with some recent
work in which Jim Lathrop, Matt Patitz, Scott Summers, and I have
explored the theoretical power and limitations of tile self-assembly.
I will also discuss the need for new specification and verification
techniques to further this exploration.

Jack Lutz completed his Ph.D. at the California Institute of
Technology in 1987.  At that time he joined the faculty at Iowa State
University, where he has been a Professor of Computer Science since
1996.  He has also held one-semester positions as a DIMACS Visiting
Fellow at Rutgers University (1990), a Visiting Professor of Computer
Science at Cornell University (1997), a Visiting Scientist at NEC
Research Institute (2001), and a Visiting Professor of Computer
Science at the University of Wisconsin at Madison (2006).  His
research interests are in computational complexity, algorithmic
information and randomness, nanoscale self-assembly, and computability
and complexity in analysis.