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).
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.