nach oben

Natural Computing

Erschienen in:

01.03.2016

Producibility in hierarchical self-assembly

Erschienen in: Natural Computing | Ausgabe 1/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Three results are shown on producibility in the hierarchical model of tile self-assembly. It is shown that a simple greedy polynomial-time strategy decides whether an assembly α is producible. The algorithm can be optimized to use \(O(|\alpha | \log ^2 |\alpha |)\) time. Cannon et al. (STACS 2013: proceedings of the thirtieth international symposium on theoretical aspects of computer science. pp 172–184, 2013) showed that the problem of deciding if an assembly α is the unique producible terminal assembly of a tile system \({\mathcal {T}}\) can be solved in \(O(|\alpha |^2 |{\mathcal {T}}| + |\alpha | |{\mathcal {T}}|^2)\) time for the special case of noncooperative “temperature 1” systems. It is shown that this can be improved to \(O(|\alpha | |{\mathcal {T}}| \log |{\mathcal {T}}|)\) time. Finally, it is shown that if two assemblies are producible, and if they can be overlapped consistently—i.e., if the positions that they share have the same tile type in each assembly—then their union is also producible .

Vorheriger Artikel Pseudo-inversion: closure properties and decidability

Nächster Artikel Computational completeness of complete, star-like, and linear hybrid networks of evolutionary processors with a small number of processors

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

This assumption does not affect the results of this paper. It is irrelevant for Theorem 5.1 or the correctness of the algorithms in the other theorems. It also does not affect the running time results for algorithms taking a TAS as input, because we can preprocess T in linear time to find and set to null any functionally null glues. The number of glues is O(|T|), and we assume that each glue from glue set G is an integer in the set \(\{0,\ldots ,|G|-1\}\). We can use a Boolean array of size |G| to determine in time O(|T|) which glues appear on the north that do not appear on the south of some tile type. Repeat this for each of the remaining three directions. Then replace all functionally null glues in T with null glues, which takes time O(|T|). To do this replacement in an assembly \(\alpha \) takes time \(O(|\alpha |)\).

For \(G^{\text{f}}_{{\text{dom}} \;\alpha }=(V_{{\text{dom}} \;\alpha },E_{{\text{dom}} \;\alpha })\) and \(G^{\text{b}}_\alpha =(V_\alpha ,E_\alpha )\), \(G^{\text{b}}_\alpha \) is a spanning subgraph of \(G^{\text{f}}_{{\text{dom}} \;\alpha }\): \(V_\alpha = V_{{\text{dom}} \;\alpha }\) and \(E_\alpha \subseteq E_{{\text{dom}} \;\alpha }\).

Intuitively \(\alpha \rightarrow _1^{\mathcal {T}} \beta \) means that \(\alpha \) can grow into \(\beta \) by the addition of a single tile; the fact that we require both \(\alpha \) and \(\beta \) to be \(\tau \)-stable implies in particular that the new tile is able to bind to \(\alpha \) with strength at least \(\tau \). It is easy to check that had we instead required only \(\alpha \) to be \(\tau \)-stable, and required that the cut of \(\beta \) separating \(\alpha \) from the new tile has strength at least \(\tau \), then this implies that \(\beta \) is also \(\tau \)-stable.

The following two convenient characterizations of “directed” are routine to verify. \({\mathcal {T}}\) is directed if and only if \(|\mathcal {A}_{\Box }[{\mathcal {T}}]| = 1\). \({\mathcal {T}}\) is not directed if and only if there exist \(\alpha ,\beta \in \mathcal {A}[{\mathcal {T}}]\) and \(p \in {\text{dom}} \;\alpha \cap {\text{dom}} \;\beta \) such that \(\alpha (p) \ne \beta (p)\).

The restriction on overlap is a model of a chemical phenomenon known as steric hindrance (Wade 1991, Section 5.11) or, particularly when employed as a design tool for intentional prevention of unwanted binding in synthesized molecules, steric protection (Heller and Pugh 1954, 1960; Goto et al. 2000).

We do not need to give the tile set T as input because the tiles in \(\alpha \) implicitly define a tile set, and the presence of extra tile types in T that do not appear in \(\alpha \) cannot affect its producibility.

Abel Z, Benbernou N, Damian M, Demaine ED, Demaine ML, Flatland R, Kominers S, Schweller R (2010) Shape replication through self-assembly and RNase enzymes. In: SODA 2010: proceedings of the twenty-first annual ACM-SIAM symposium on discrete algorithms, Austin, Texas. Society for Industrial and Applied Mathematics

Adleman LM, Cheng Q, Goel A, Huang MDA, Kempe D, de Espanés PM, Rothemund PWK (2002) Combinatorial optimization problems in self-assembly. In: STOC 2002: proceedings of the thirty-fourth annual ACM symposium on theory of computing, pp 23–32 (2002)

Aggarwal G, Cheng Q, Goldwasser MH, Kao M-Y, de Espanés PM, Schweller RT (2005) Complexities for generalized models of self-assembly. SIAM J Comput 34:1493–1515 Preliminary version appeared in SODA 2004

Barish RD, Schulman R, Rothemund PWK, Winfree E (2009) An information-bearing seed for nucleating algorithmic self-assembly. Proc Nat Acad Sci 106(15):6054–6059CrossRef

Cannon S, Demaine ED, Demaine ML, Eisenstat S, Patitz MJ, Schweller RT, Summers SM. Winslow A (2013) Two hands are better than one (up to constant factors). In: STACS 2013: proceedings of the thirtieth international symposium on theoretical aspects of computer science, pp 172–184

Chen H-L, Doty D (2012) Parallelism and time in hierarchical self-assembly. In: SODA 2012: proceedings of the 23rd annual ACM-SIAM symposium on discrete algorithms, pp 1163–1182

Chen H-L, Doty D, Maňuch J, Rafiey A, Stacho L (2015, to appear) Pattern overlap implies runaway growth in hierarchical tile systems. In: SoCG 2015: proceedings of the 31st international symposium on computational geometry

Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Introduction to algorithms. MIT Press, CambridgeMATH

Demaine ED, Demaine ML, Fekete SP, Ishaque M, Rafalin E, Schweller RT, Souvaine DL (2008) Staged self-assembly: nanomanufacture of arbitrary shapes with \({O}(1)\) glues. Nat Comput 7(3):347–370 Preliminary version appeared in DNA (2007)

Demaine ED, Eisenstat S, Ishaque M, Winslow A (2013) One-dimensional staged self-assembly. Nat Comput 12(2):1–12 Preliminary version appeared in DNA 2011

Demaine ED, Patitz MJ, Rogers T, Schweller RT, Summers SM, Woods D (2013) The two-handed tile assembly model is not intrinsically universal. In: ICALP 2013: proceedings of the 40th international colloquium on automata, languages and programming, July 2013

Demaine ED, Patitz MJ, Schweller RT, Summers SM (2011) Self-assembly of arbitrary shapes using RNase enzymes: meeting the Kolmogorov bound with small scale factor. In: STACS 2011: proceedings of the 28th international symposium on theoretical aspects of computer science

Doty D (2012) Theory of algorithmic self-assembly. Commun ACM 55(12):78–88CrossRef

Doty D, Lutz Jack H, Patitz MJ, Schweller RT, Summers SM, Woods D (2012) The tile assembly model is intrinsically universal. In: FOCS 2012: proceedings of the 53rd annual IEEE symposium on foundations of computer science, pp 302–310

Doty D, Patitz MJ, Reishus D, Schweller RT, Summers SM (2010) Strong fault-tolerance for self-assembly with fuzzy temperature. In: FOCS 2010: proceedings of the 51st annual IEEE symposium on foundations of computer science, pp 417–426

Fu B, Patitz MJ, Schweller RT, Sheline R (2012) Self-assembly with geometric tiles. In: ICALP 2012: proceedings of the 39th international colloquium on automata, languages and programming, pp 714–725, July 2012

Goto K, Hinob Y, Kawashima T, Kaminagab M, Yanob E, Yamamotob G, Takagic N, Nagasec S (2000) Synthesis and crystal structure of a stable S-nitrosothiol bearing a novel steric protection group and of the corresponding S-nitrothiol. Tetrahedron Lett 41(44):8479–8483CrossRef

Heller W, Pugh TL (1954) “Steric protection” of hydrophobic colloidal particles by adsorption of flexible macromolecules. J Chem Phys 22(10):1778

Heller W, Pugh TL (1960) “Steric” stabilization of colloidal solutions by adsorption of flexible macromolecules. J Polym Sci 47(149):203–217CrossRef

Hopcroft J, Tarjan R (1973) Algorithm 447: efficient algorithms for graph manipulation. Commun ACM 16(6):372–378CrossRef

Lathrop JI, Lutz JH, Summers SM (2009) Strict self-assembly of discrete Sierpinski triangles. Theor Comput Sci 410:384–405 Preliminary version appeared in CiE (2007) CrossRefMathSciNetMATH

Luhrs C (2010) Polyomino-safe DNA self-assembly via block replacement. Nat Comput 9(1):97–109 Preliminary version appeared in DNA 2008 CrossRefMathSciNetMATH

Patitz MJ (2012) An introduction to tile-based self-assembly. In: UCNC 2012: proceedings of the 11th international conference on unconventional computation and natural computation. Springer, Berlin, pp 34–62

Patitz MJ, Summers SM (2012) Identifying shapes using self-assembly. Algorithmica 64(3):481–510 Preliminary version appeared in ISAAC (2010) CrossRefMathSciNetMATH

Rothemund PWK (2001) Theory and experiments in algorithmic self-assembly. PhD thesis, University of Southern California, December 2001

Rothemund PWK, Winfree E (2000) The program-size complexity of self-assembled squares (extended abstract). In: STOC 2000: proceedings of the thirty-second annual ACM symposium on theory of computing, pp 459–468

Schulman R, Winfree E (2007) Synthesis of crystals with a programmable kinetic barrier to nucleation. Proc Nat Acad Sci 104(39):15236–15241CrossRef

Schulman R, Winfree E (2009) Programmable control of nucleation for algorithmic self-assembly. SIAM J Comput 39(4):1581–1616 Preliminary version appeared in DNA 2004 CrossRefMathSciNetMATH

Schweller RT, Sherman M (2013) Fuel efficient computation in passive self-assembly. In: SODA 2013: proceedings of the 24th annual ACM-SIAM symposium on discrete algorithms, pp 1513–1525, January (2013)

Wade LG (1991) Organic chemistry. Prentice Hall, Englewood Cliffs

Winfree E (1998) Algorithmic self-assembly of DNA. PhD thesis, California Institute of Technology, June 1998

Winfree E (1998) Simulations of computing by self-assembly. Technical Report CaltechCSTR:1998.22, California Institute of Technology

Winfree E (2006) Self-healing tile sets. In: Chen J, Jonoska N, Rozenberg G (eds) Nanotechnology: science and computation, natural computing series. Springer, Berlin, pp 55–78CrossRef

Winfree E, Liu F, Wenzler LA, Seeman NC (1998) Design and self-assembly of two-dimensional DNA crystals. Nature 394(6693):539–44CrossRef

Winslow A (2013) Staged self-assembly and polyomino context-free grammars. In: DNA 2013: proceedings of the 19th international meeting on DNA computing and molecular programming

Titel: Producibility in hierarchical self-assembly
Publikationsdatum: 01.03.2016
Erschienen in: Natural Computing / Ausgabe 1/2016
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-015-9517-2

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 1/2016

Synthetic biology of cell signaling

Halting the hallmarks: a cellular automaton model of early cancer growth inhibition

Counter machines and crystallographic structures

A quantum particle swarm optimization for the 0–1 generalized knapsack sharing problem

Fast arithmetic in algorithmic self-assembly

Evolution of new algorithms for the binary knapsack problem