Discrete Mathematics and Optimization Seminar

Ed Coffman
Columbia University
Monday November 5th at 4.30pm
Burnside 1205

Title. Self-Assembly Times in the Tile Model of Molecular Computation.

Abstract. Advances in chemical synthesis have laid the groundwork for computation
at nanoscale, where self assembly becomes the core process, either as a
computation itself, or as a mechanism for fabricating nanodevices.
By such processes, elementary particles, such as DNA molecules, combine
into large complexes following built-in bonding rules. Such molecules
are naturally modeled by Wang-like tiles proposed by Winfree. We study self assembly
viewed as a random growth (tiling) process, addressing such as questions as:``How
long does a given pattern take to self-assemble?'' ``How does one optimize the
yield of a particular self-assembly process?'' ``What are the
trade-offs between the reliability (error tolerance) and speed of
self assembly?'' Answers to these questions bring out unexpected
connections with classical areas of mathematics.
The talk begins with a brief tutorial on DNA-based computing, segues into
a discussion of the Winfree/Rothemund tile model, and concludes with an
analysis of tiling rates via the TASEP and the Hammersley process.