skip to main content
10.1145/1529282.1529453acmconferencesArticle/Chapter ViewAbstractPublication PagessacConference Proceedingsconference-collections
research-article

Two lower bounds for self-assemblies at temperature 1

Published: 08 March 2009 Publication History

Abstract

Self-assembly is an autonomous process by which small simple parts assemble into larger and more complex objects. Self-assembly occurs in nature, for example, when atoms combine to form molecules, and molecules combine to form crystals. It has been suggested that intricate self-assembly schemes will ultimately be useful for circuit fabrication, nanorobotics, DNA computing, and amorphous computing [2, 7]. To study the process of self-assembly we use the Tile Assembly Model proposed by Rothemund and Winfree [5]. This model considers the assembly of square blocks called "tiles" and a set of glues called "binding domains". Each binding domain has a strength. Each of the four sides of a tile can have a glue on it that determines interactions with neighbouring tiles. The two neighbouring tiles form a bond if the binding domains on the touching sides are the same. The strength of this bond is the strength of the matching binding domain. The process of self-assembly is initiated by a single seed tile and proceeds by attaching tiles one by one. A tile can only attach to the growing complex if it binds strongly enough, i.e., if the sum of the strengths of its bonds to the existing complex is at least the temperature τ. It is assumed that there is an infinite supply of tiles of each tile type. When this growing process stops, i.e., no tile can be attached to the existing complex, we say that the tile system has assembled this shape. A tile system is specified by the seed tile, the set of tile types, the strengths of glues and the temperature.
The physical plausibility and relevance of this abstraction was demonstrated by simple self-assembling systems of tiles built out of certain types of DNA molecules [3, 4]. In this paper we only consider self-assembly at temperature τ = 1. Self-assemblies at temperature τ > 1 have been considered in [5, 6, 1].
A measure of complexity of self-assembly is the minimum number of distinct tile types needed to uniquely assemble a certain shape (assembles the shape but does not assemble any other shape). If we want to assemble any scaled version of a given shape, then the complexity depends on the expressibility (Kolmogorov complexity) of the shape [6]. If we want to assemble a given shape with a prescribed size, then in [5] it was observed that assembling an N x N full square (a square where there is a bond between any two adjacent tiles) at τ = 1 requires N2 distinct tile types. In fact, one can see that any uniquely produced 2-connected full assembly with p tiles requires p tile types (all tiles must be distinct). If we do not require a bond between every two adjacent tiles of a uniquely produced assembly the number of used tile types can be significantly smaller. In particular, in [5] a tile system that uniquely assembles an N x N square using only 2N - 1 tile types was described. The construction is based on a comb-like backbone graph of the N x N square. Moreover, it was conjectured in [5] that this is best possible.

References

[1]
L. Adleman, Q. Cheng, A. Goel, M.-D. Huang, D. Kempe, P. de Espanes, and P. Rothemund. Combinatorial optimization problems in self-assembly. In Proceedings of STOC, pages 23--32, 2002.
[2]
M. Gomez-Lopez, J. Preece, and J. Stoddart. The art and science of self-assembling molecular machines. Nanotechnology, 7: 183--192, 1996.
[3]
T. LaBean, H. Yan, J. Kopatsch, F. Liu, E. Winfree, J. Reif, and N. Seeman. Construction, analysis, ligation, and self-assembly of DNA triple crossover complexes. Journal of the American Chemical Society, 122: 1848--1860, 2000.
[4]
P. Rothemund, N. Papadakis, and E. Winfree. Algorithmic self-assembly of DNA sierpinski triangles. PLoS Biology, 2: 2041--2053, 2004.
[5]
P. Rothemund and E. Winfree. The program-size complexity of self-assembled squares. In Proceedings of STOC, pages 459--468, 2000.
[6]
D. Soloveichik and E. Winfree. Complexity of self-assembled shapes. SIAM Journal on Computing, 36: 1544--1569, 2007.
[7]
G. Whitesides, J. Mathias, and C. Seto. Molecular self-assembly and nanochemistry: a chemical strategy for the synthesis of nanostructures. Science, 254: 1312--1319, 1991.

Cited By

View all
  • (2011)Temperature 1 self-assemblyProceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms10.5555/2133036.2133081(570-589)Online publication date: 23-Jan-2011

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
SAC '09: Proceedings of the 2009 ACM symposium on Applied Computing
March 2009
2347 pages
ISBN:9781605581668
DOI:10.1145/1529282
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 March 2009

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Research-article

Conference

SAC09
Sponsor:
SAC09: The 2009 ACM Symposium on Applied Computing
March 8, 2009 - March 12, 2008
Hawaii, Honolulu

Acceptance Rates

Overall Acceptance Rate 1,650 of 6,669 submissions, 25%

Upcoming Conference

SAC '25
The 40th ACM/SIGAPP Symposium on Applied Computing
March 31 - April 4, 2025
Catania , Italy

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)0
Reflects downloads up to 19 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2011)Temperature 1 self-assemblyProceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms10.5555/2133036.2133081(570-589)Online publication date: 23-Jan-2011

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media