nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

Resiliency to Multiple Nucleation in Temperature-1 Self-Assembly

verfasst von : Matthew J. Patitz, Trent A. Rogers, Robert T. Schweller, Scott M. Summers, Andrew Winslow

Erschienen in: DNA Computing and Molecular Programming

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We consider problems in variations of the two-handed abstract Tile Assembly Model (2HAM), a generalization of Erik Winfree’s abstract Tile Assembly Model (aTAM). In the latter, tiles attach one-at-a-time to a seed-containing assembly. In the former, tiles aggregate into supertiles that then further combine to form larger supertiles; hence, constructions must be robust to the choice of seed (nucleation) tiles. We obtain three distinct results in two 2HAM variants whose aTAM siblings are well-studied.

In the first variant, called the restricted glue 2HAM (rg2HAM), glue strengths are restricted to \(-1\), 0, or 1. We prove this model is Turing universal, overcoming undesired growth by breaking apart undesired computation assembly via repulsive forces.

In the second 2HAM variant, the 3D 2HAM (3D2HAM), tiles are (three-dimensional) cubes. We prove that assembling a (roughly two-layer) \(n \times n\) square in this model is possible with \(O(\log ^2{n})\) tile types. The construction uses “cyclic, colliding” binary counters, and assembles the shape non-deterministically. Finally, we prove that there exist 3D2HAM systems that only assemble infinite aperiodic shapes.

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

Vorheriges Kapitel Hierarchical Self-Assembly of Fractals with Signal-Passing Tiles

Nächstes Kapitel Verifying Chemical Reaction Network Implementations: A Bisimulation Approach

Such a distinction is only needed in two-handed models, where the seed cannot be used as a “reference point”.

Adleman, L., Cheng, Q., Goel, A., Huang, M.-D.: Running time and program size for self-assembled squares. In: Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC), pp. 740–748 (2001)

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

Berger, R.: The undecidability of the domino problem. Mem. Am. Math. Soc. 66, 1–72 (1966)MathSciNetMATH

Cannon, S., Demaine, E.D., Demaine, M.L., Eisenstat, S., Patitz, M.J., Schweller, R., Summers, S.M., Winslow, A.: Two hands are better than one (up to constant factors): self-assembly in the 2HAM vs. aTAM. In: Proceedings of 30th International Symposium on Theoretical Aspects of Computer Science (STACS). LIPIcs, vol. 20, pp. 172–184. Schloss Dagstuhl (2013)

Chen, H.-L., Doty, D., Manuch, J., Rafiey, A., Stacho, L.: Pattern overlap implies runaway growth in hierarchical tile systems. In: Arge, L., Pach, J. (eds.) 31st International Symposium on Computational Geometry (SoCG). LIPIcs, vol. 34, pp. 360–373. Schloss Dagstuhl (2015)

Chen, H.-L., Schulman, R., Goel, A., Winfree, E.: Reducing facet nucleation during algorithmic self-assembly. Nano Lett. 7(9), 2913–2919 (2007)CrossRef

Cook, M., Fu, Y., Schweller, R.T.: Temperature 1 self-assembly: deterministic assembly in 3D and probabilistic assembly in 2D. In: Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, pp. 570–589 (2011)

Demaine, E.D., Demaine, M.L., Fekete, S.P., Ishaque, M., Rafalin, E., Schweller, R.T., Souvaine, D.L.: Staged self-assembly: nanomanufacture of arbitrary shapes with \({O}(1)\) glues. Nat. Comput. 7(3), 347–370 (2008)MathSciNetCrossRefMATH

Doty, D.: Producibility in hierarchical self-assembly. Nat. Comput. 15(1), 41–49 (2016)MathSciNetCrossRefMATH

10.

Doty, D., Patitz, M.J., Summers, S.M.: Limitations of self-assembly at temperature 1. Theor. Comput. Sci. 412, 145–158 (2011)MathSciNetCrossRefMATH

11.

Fekete, S.P., Hendricks, J., Patitz, M.J., Rogers, T.A., Schweller, R.T.: Universal computation with arbitrary polyomino tiles in non-cooperative self-assembly. In: Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, pp. 148–167. SIAM (2015)

12.

Goodman-Strauss, C.: Open questions in tiling (2000). http://comp.uark.edu/strauss/papers/survey.pdf

13.

Grünbaum, B., Shephard, G.C.: Tilings and Patterns. W.H. Freeman and Company, New York (1987)MATH

14.

Meunier, P.-E., Patitz, M.J., Summers, S.M., Theyssier, G., Woods, D.: Intrinsic universality in tile self-assembly requires cooperation. In: Proceedings of the 25th Symposium on Discrete Algorithms (SODA), pp. 752–771 (2014)

15.

Padilla, J.E., et al.: Asynchronous signal passing for tile self-assembly: fuel efficient computation and efficient assembly of shapes. In: Mauri, G., Dennunzio, A., Manzoni, L., Porreca, A.E. (eds.) UCNC 2013. LNCS, vol. 7956, pp. 174–185. Springer, Heidelberg (2013)CrossRef

16.

Patitz, M.J., Schweller, R.T., Summers, S.M.: Exact shapes and turing universality at temperature 1 with a single negative glue. In: Cardelli, L., Shih, W. (eds.) DNA 17 2011. LNCS, vol. 6937, pp. 175–189. Springer, Heidelberg (2011)CrossRef

17.

Rothemund, P.W.K., Winfree, E.: The program-size complexity of self-assembled squares (extended abstract). In: Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC), pp. 459–468 (2000)

18.

Schulman, R.: The self-replication and evolution of DNA crystals. PhD thesis (2007)

19.

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

20.

Schulman, R., Winfree, E.: Programmable control of nucleation for algorithmic self-assembly. SIAM J. Comput. 39(4), 1581–1616 (2009)MathSciNetCrossRefMATH

21.

Seeman, N.C.: Nucleic-acid junctions and lattices. J. Theor. Biol. 99, 237–247 (1982)CrossRef

22.

Socolar, J.E.S., Taylor, J.M.: An aperiodic hexagonal tile. J. Comb. Theor. Series A 118(8), 2207–2231 (2011)MathSciNetCrossRefMATH

23.

Soloveichik, D., Winfree, E.: Complexity of self-assembled shapes. SIAM J. Comput. 36(6), 1544–1569 (2007)MathSciNetCrossRefMATH

24.

Winfree, E.: Algorithmic self-assembly of DNA. PhD thesis, Caltech (1998)

Titel: Resiliency to Multiple Nucleation in Temperature-1 Self-Assembly
verfasst von: Matthew J. Patitz
Trent A. Rogers
Robert T. Schweller
Scott M. Summers
Andrew Winslow
Verlag: Springer International Publishing
Buch: DNA Computing and Molecular Programming
Print ISBN: 978-3-319-43993-8

Electronic ISBN: 978-3-319-43994-5

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-319-43994-5_7

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"

Premium Partner