Back to the program.
Nanoscale Staged Self-Assembly
Andrew Winslow
On 2014-10-24 at 13:00:00 (Brussels Time)

Abstract

In all forms of life, molecules are propelled by Brownian motion to interact, communicate, and aggregate, carrying out unbelievably varied and complex behaviors. In the last twenty years, biochemists have taken inspiration from the nature to design systems consisting entirely of short strands of DNA that algorithmically self-assemble into programmed crystalline structures. These systems compute, but in an asynchronous, decentralized, and geometric way. As the robustness and complexity of these systems has improved, developing a theory of algorithmic self-assembly has become important. Our work studies a variation of perhaps the most well-studied formal model of nanoscale self-assembly: Erik Winfree's abstract tile assembly model (aTAM). In this variation, a system is broken into stages: particles assemble to form superstructures that subsequently combine with other formed superstructures. This variation addresses a key scalability issue in the original aTAM, but enables far more varied system design. Our main contribution is a comparison between context-free grammars, a classic model of computation, and the staged self-assembly model. This comparison enables us to provide upper and lower bounds on the capabilities of staged nanoscale self-assembly, including novel algorithms and lower bounds for the complexity of optimizing these systems. Joint work with Erik Demaine, Sarah Eisenstat, and Mashhood Ishaque.

Keywords

Biocomputing, DNA Computing, Algorithmic Self-Assembly

References

  1. E. D. Demaine, S. Eisenstat, M. Ishaque, A. Winslow. (2011) One-dimensional staged self-assembly. In L. Cardelli and W. Shih (ed.) DNA 17. Springer, Heidelberg Berlin. pp. 100-114.
    See http://www.eecs.tufts.edu/~awinslow/papers/nanogrammar-dna11.pdf
  2. A. Winslow. (2013) Staged self-assembly and polyomino context-free grammars. In Staged self-assembly and polyomino context-free grammars (ed.) DNA 19. Springer, Heidelberg Berlin. pp. 174-188.
    See http://www.eecs.tufts.edu/~awinslow/papers/nanogrammar2-dna13.pdf