Scott Summers

University of Wisconsin
Homepage


Two Hands Are Better Than One (in Self-Assembly)

ABSTRACT

Perhaps the simplest mathematical model of algorithmic DNA tile self-assembly is Erik Winfree's abstract Tile Assembly Model (aTAM). The aTAM is a deliberately over-simplified, combinatorial model of nanoscale DNA tile self-assembly that "effectivizes" classical Wang tiling in the sense that the former augments the latter with a mechanism for sequential "growth" of a tile assembly. Very briefly, in the aTAM, the fundamental components are un-rotatable, translatable square "tile types" whose sides are labeled with (alpha-numeric) glue "colors" and (integer) "strengths". Two tiles that are placed next to each other interact if the glue colors on their abutting sides match, and they bind if the strengths on their abutting sides match and sum to at least a certain (integer) ``temperature''. Self-assembly starts from a "seed" tile type, typically assumed to be placed at the origin, and proceeds nondeterministically and asynchronously as tiles bind to the seed-containing assembly one tile at a time.

The Two-Handed Tile Assembly Model (2HAM) (also known as Hierarchical Self-Assembly) is essentially an unseeded generalization of the aTAM, in which any two assemblies (including but not limited to individual tiles) can fuse to each other. Instead of using seeds, the 2HAM defines the "output" of the system to consist of all assemblies that cannot be fused with any others possibly produced by the system.

In this talk, we will give brief introductions to the aTAM and 2HAM as well as highlight some key differences between these two tile self-assembly models. The results we mention in this talk will suggest that, in most cases, that the aTAM is at most as powerful as the 2HAM, i.e. aTAM = O(2HAM), and in certain cases, the 2HAM is strictly more powerful than the aTAM, i.e., aTAM = o(2HAM). Specific topics to be highlighted include the following: (1) simulation of the aTAM by the 2HAM with a O(1) scale factor, (2) the existence of a class of shapes that can be uniquely self-assembled in the 2HAM using asymptotically fewer unique tile types than any aTAM system, and (3) the algorithmic complexity of verifying properties of 2HAM systems, e.g., whether a 2HAM system uniquely produces a given 3D assembly (known to be in P for 3D aTAM systems).


BIOGRAPHY

Scott Summers is an assistant professor of Computer Science at the University of Wisconsin -- Oshkosh. He received his PhD in Computer Science from Iowa State University in 2010. Currently, his primary research interests are in theoretical Computer Science, but specifically in the theory of algorithmic tile self-assembly. Within tile self-assembly, he is interested in studying intrinsic universality in self-assembly, models of fault-tolerance for self-assembly, lower-bound techniques in self-assembly and non-cooperative self-assembly. He has co-authored many papers in tile self-assembly over the past several years that have appeared in such theoretical Computer Science conferences and journals as FOCS, SODA, ICALP, STACS, ISAAC, DNA and Algorithmica.


Back to the UCNC 2014 main page