Paper by Erik D. Demaine

Reference:

Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Mashhood Ishaque, Eynat Rafalin, Robert T. Schweller, and Diane L. Souvaine, “Staged Self-Assembly: Nanomanufacture of Arbitrary Shapes with O(1) Glues”, in Proceedings of the 13th International Meeting on DNA Computing (DNA 2007), Lecture Notes in Computer Science, volume 4848, Memphis, Tennessee, June 4–8, 2007, pages 1–14.

BibTeX

@InProceedings{StagedAssembly_DNA2007,
  AUTHOR        = {Erik D. Demaine and Martin L. Demaine and
                   S\'andor P. Fekete and Mashhood Ishaque and
                   Eynat Rafalin and Robert T. Schweller and Diane L. Souvaine},
  TITLE         = {Staged Self-Assembly: Nanomanufacture of Arbitrary Shapes
                   with $O(1)$ Glues},
  BOOKTITLE     = {Proceedings of the 13th International Meeting on
                   DNA Computing (DNA 2007)},
  bookurl       = {http://dna13.memphis.edu/},
  SERIES        = {Lecture Notes in Computer Science},
  seriesurl     = {http://www.springer.de/comp/lncs/},
  VOLUME        = 4848,
  ADDRESS       = {Memphis, Tennessee},
  MONTH         = {June 4--8},
  YEAR          = 2007,
  PAGES         = {1--14},

  doi           = {https://dx.doi.org/10.1007/978-3-540-77962-9_1},
  dblp          = {https://dblp.org/rec/conf/dna/DemaineDFIRSS07},
  comments      = {This paper is also available from <A HREF="http://dx.doi.org/10.1007/978-3-540-77962-9_1">SpringerLink</A>.},
  award         = {Invited to special issue of \emph{Natural Computing}.},
  papers        = {StagedAssembly_NACO},
  updates       = {The tile bound of 16 in Table 1 row 5 (arbitrary shape)
                   and in Theorem 5 is incorrect; the correct bound
                   (for the same algorithm) is 52.}
}

Abstract:

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.

Comments:

This paper is also available from SpringerLink.

Updates:

The tile bound of 16 in Table 1 row 5 (arbitrary shape) and in Theorem 5 is incorrect; the correct bound (for the same algorithm) is 52.

Availability:

The paper is available in PDF (189k).

See information on file formats.

[Google Scholar search]

Related papers:

StagedAssembly_NACO (Staged Self-Assembly: Nanomanufacture of Arbitrary Shapes with O(1) Glues)