  We introduce staged self-assembly of Wang tiles, where tiles can be added
dynamically in sequence and where intermediate constructions can be stored for
later mixing. This model and its various constraints and performance measures
are motivated by a practical nanofabrication scenario through protein-based
bioengineering. Staging allows us to break through the traditional lower bounds
in tile self-assembly by encoding the shape in the staging algorithm instead of
the tiles. All of our results are based on the practical assumption that only a
constant number of glues, and thus only a constant number of tiles, can be
engineered, as each new glue type requires significant biochemical research and
experiments. Under this assumption, traditional tile self-assembly cannot even
manufacture an n*n square; in contrast, we show how staged assembly enables
manufacture of arbitrary orthogonal shapes in a variety of precise formulations
of the model.
