|Discrete Mathematics and Optimization Seminar
Monday November 5th at 4.30pm
Title. Self-Assembly Times in the Tile Model of Molecular Computation.
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.