Theory and experiments in algorithmic self-assembly

Self-assembly plays a central role in the organization of matter; out of basic units ranging from atoms to stars, self-assembly creates complex patterns ranging from crystals to galaxies. Investigations of DNA computing have revealed a fundamental connection between self-assembly and computation: in principle, any computation can be performed by a suitable self-assembling system.; Here, we study this connection both theoretically and experimentally. We begin with a theoretical study of square tiles, known as Wang tiles, using the Tile Assembly Model (TAM). The TAM models temperature and other experimental conditions using an integer parameter tau. We study the TAM at tau = 1, under which tiles may bind to an aggregate via single bonds, and at tau = 2 under which tiles must bind by at least two bonds. For tau = 2 we find that an efficient O(log N) complexity can be achieved whereas for tau = 1 we prove that the complexity is exactly N2. The exponential improvement for tau = 2 is achieved by simulating a binary counter; hence, while universal computation can be performed by self-assembly under both conditions, it appears that computation can be used to greater effect at tau = 2.; Real systems likely lie between tau = 1 and tau = 2; finding systems that approximate tau = 2 is an important goal---such systems would open the door for the use of computation in self-assembly. Toward this end we explore an experimental system in which plastic tiles self-assemble via capillary forces. We test the system's ability to compute using a set of "XOR" tiles that would simulate a well-known cellular automaton if tau = 2 but would assemble with errors if tau = 1. Our experiments show that the XOR tiles assemble with few errors; thus they exhibit tau = 2-like behavior.; Finally, we begin to explore error rates and nucleation in a DNA-based system. We design DNA tiles to form 2D lattices bearing a pattern of stripes readily visible under the atomic force microscope. Error-free (tau = 2) growth would result in a pattern of continuous stripes; errors would result in broken stripes. Initial experiments show that errors can be visualized allowing future studies to optimize conditions for tau = 2 growth.