Skip to main content
Top
Published in: Natural Computing 2/2015

01-06-2015

Signal transmission across tile assemblies: 3D static tiles simulate active self-assembly by 2D signal-passing tiles

Authors: Tyler Fochtman, Jacob Hendricks, Jennifer E. Padilla, Matthew J. Patitz, Trent A. Rogers

Published in: Natural Computing | Issue 2/2015

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The 2-handed assembly model (2HAM) is a tile-based self-assembly model in which, typically beginning from single tiles, arbitrarily large aggregations of static tiles combine in pairs to form structures. The signal-passing tile assembly model (STAM) is an extension of the 2HAM in which the tiles are dynamically changing components which are able to alter their binding domains as they bind together. In this paper, we examine the \(\hbox {STAM}^+\), a restriction of the STAM that does not allow glues to be turned “off”, and prove that there exists a 3D tile set at temperature \(\tau >1\) in the 2HAM which is intrinsically universal for the class of all 2D \(\hbox {STAM}^+\) systems at temperature \(\tau \) for each \(\tau \) (where the \(\hbox {STAM}^+\) does not make use of the STAM’s power of glue deactivation and assembly breaking, as the tile components of the 2HAM are static and unable to change or break bonds). This means that there is a single tile set \(U\) in the 3D 2HAM which can, for an arbitrarily complex \(\hbox {STAM}^+\) system \(S\), be configured with a single input configuration which causes \(U\) to exactly simulate \(S\) at a scale factor dependent upon \(S\). Furthermore, this simulation uses only two planes of the third dimension. This implies that there exists a 3D tile set at temperature \(2\) in the 2HAM which is intrinsically universal for the class of all 2D \(\hbox {STAM}^+\) systems at temperature \(1\). Moreover, we also show that there exists an \(\hbox {STAM}^+\) tile set for temperature \(\tau \) which is intrinsically universal for the class of all 2D \(\hbox {STAM}^+\) systems at temperature \(\tau \), including the case where \(\tau = 1\). To achieve these results, we also demonstrate useful techniques and transformations for converting an arbitrarily complex \(\hbox {STAM}^+\) tile set into an \(\hbox {STAM}^+\) tile set where every tile has a constant, low amount of complexity, in terms of the number and types of “signals” they can send, with a trade off in scale factor. While the first result is of more theoretical interest, showing the power of static tiles to simulate dynamic tiles when given one extra plane in 3D, the second result is of more practical interest for the experimental implementation of STAM tiles, since it provides potentially useful strategies for developing powerful STAM systems while keeping the complexity of individual tiles low, thus making them easier to physically implement.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

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!

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!

Literature
go back to reference Abel Z, Benbernou N, Damian M, Demaine ED, Demaine ML, Flatland R, Kominers SD, Schweller RT (2010) Shape replication through self-assembly and rnase enzymes. In: Proceedings of the twenty-first annual ACM-SIAM symposium on discrete algorithms, pp 1045–1064 Abel Z, Benbernou N, Damian M, Demaine ED, Demaine ML, Flatland R, Kominers SD, Schweller RT (2010) Shape replication through self-assembly and rnase enzymes. In: Proceedings of the twenty-first annual ACM-SIAM symposium on discrete algorithms, pp 1045–1064
go back to reference Becker F, Rapaport I, Rémila E (2006) Self-assembling classes of shapes with a minimum number of tiles, and in optimal time. In: Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pp 45–56 Becker F, Rapaport I, Rémila E (2006) Self-assembling classes of shapes with a minimum number of tiles, and in optimal time. In: Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pp 45–56
go back to reference Chandran H, Gopalkrishnan N, Reif JH (2009) The tile complexity of linear assemblies. In: Albers S, Marchetti-Spaccamela A, Matias Y, Nikoletseas SE, Thomas W (eds) Automata, languages and programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5–12, 2009, proceedings, part I. Lecture Notes in Computer Science, vol 5555. Springer, Berlin, pp 235–253 Chandran H, Gopalkrishnan N, Reif JH (2009) The tile complexity of linear assemblies. In: Albers S, Marchetti-Spaccamela A, Matias Y, Nikoletseas SE, Thomas W (eds) Automata, languages and programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5–12, 2009, proceedings, part I. Lecture Notes in Computer Science, vol 5555. Springer, Berlin, pp 235–253
go back to reference Cheng Q, Aggarwal G, Goldwasser MH, Kao M-Y, Schweller RT, de Espanés PM (2005) Complexities for generalized models of self-assembly. SIAM J Comput 34:1493–1515MATHMathSciNet Cheng Q, Aggarwal G, Goldwasser MH, Kao M-Y, Schweller RT, de Espanés PM (2005) Complexities for generalized models of self-assembly. SIAM J Comput 34:1493–1515MATHMathSciNet
go back to reference Cook M, Fu Y, Schweller R (2011) Temperature 1 self-assembly: deterministic assembly in 3d and probabilistic assembly in 2d. In: Proceedings of the twenty-second annual ACM-SIAM symposium on discrete algorithms, SODA ’11, SIAM, pp 570–589 Cook M, Fu Y, Schweller R (2011) Temperature 1 self-assembly: deterministic assembly in 3d and probabilistic assembly in 2d. In: Proceedings of the twenty-second annual ACM-SIAM symposium on discrete algorithms, SODA ’11, SIAM, pp 570–589
go back to reference Costa Santini C, Bath J, Tyrrell AM, Turberfield AJ (2013) A clocked finite state machine built from DNA. Chem Commun 49:237–239 Costa Santini C, Bath J, Tyrrell AM, Turberfield AJ (2013) A clocked finite state machine built from DNA. Chem Commun 49:237–239
go back to reference Delorme M, Mazoyer J, Ollinger N, Theyssier G (2011a) Bulking I: an abstract theory of bulking. Theor Comput Sci 412(30):3866–3880MATHMathSciNet Delorme M, Mazoyer J, Ollinger N, Theyssier G (2011a) Bulking I: an abstract theory of bulking. Theor Comput Sci 412(30):3866–3880MATHMathSciNet
go back to reference Delorme M, Mazoyer J, Ollinger N, Theyssier G (2011b) Bulking II: classifications of cellular automata. Theor Comput Sci 412(30):3881–3905MATHMathSciNet Delorme M, Mazoyer J, Ollinger N, Theyssier G (2011b) Bulking II: classifications of cellular automata. Theor Comput Sci 412(30):3881–3905MATHMathSciNet
go back to reference 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–370MATHMathSciNet 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–370MATHMathSciNet
go back to reference Demaine ED, Patitz MJ, Rogers TA, Schweller RT, Summers SM, Woods D (2013) The two-handed assembly model is not intrinsically universal. In: 40th International Colloquium on Automata, Languages and Programming, ICALP 2013, Riga, Latvia, July 8–12, 2013. Lecture notes in computer science. Springer, Berlin Demaine ED, Patitz MJ, Rogers TA, Schweller RT, Summers SM, Woods D (2013) The two-handed assembly model is not intrinsically universal. In: 40th International Colloquium on Automata, Languages and Programming, ICALP 2013, Riga, Latvia, July 8–12, 2013. Lecture notes in computer science. Springer, Berlin
go back to reference Doty D, Kari L, Masson B (2013) Negative interactions in irreversible self-assembly. Algorithmica 66:153–172; preliminary version appeared in DNA 2010 Doty D, Kari L, Masson B (2013) Negative interactions in irreversible self-assembly. Algorithmica 66:153–172; preliminary version appeared in DNA 2010
go back to reference Doty D, Lutz JH, Patitz MJ, Schweller RT, Summers SM, Woods D (2012) The tile assembly model is intrinsically universal. In Proceedings of the 53rd annual IEEE symposium on foundations of computer science, FOCS 2012, pp 302–310 Doty D, Lutz JH, Patitz MJ, Schweller RT, Summers SM, Woods D (2012) The tile assembly model is intrinsically universal. In Proceedings of the 53rd annual IEEE symposium on foundations of computer science, FOCS 2012, pp 302–310
go back to reference Fu B, Patitz MJ, Schweller RT, Sheline R (2012) Self-assembly with geometric tiles. In: Proceedings of the 39th international colloquium on automata, languages and programming, ICALP, to appear Fu B, Patitz MJ, Schweller RT, Sheline R (2012) Self-assembly with geometric tiles. In: Proceedings of the 39th international colloquium on automata, languages and programming, ICALP, to appear
go back to reference Han D, Pal S, Yang Y, Jiang S, Nangreave J, Liu Y, Yan H (2013) DNA gridiron nanostructures based on four-arm junctions. Science 339(6126):1412–1415CrossRef Han D, Pal S, Yang Y, Jiang S, Nangreave J, Liu Y, Yan H (2013) DNA gridiron nanostructures based on four-arm junctions. Science 339(6126):1412–1415CrossRef
go back to reference Hendricks J, Padilla JE, Patitz MJ, Rogers TA (2013) Signal transmission across tile assemblies: 3D static tiles simulate active self-assembly by 2D signal-passing tiles. In: Soloveichik D, Yurke B (eds) DNA computing and molecular programming. Lecture notes in computer science, vol 8141. Springer, Berlin, pp 90–104CrossRef Hendricks J, Padilla JE, Patitz MJ, Rogers TA (2013) Signal transmission across tile assemblies: 3D static tiles simulate active self-assembly by 2D signal-passing tiles. In: Soloveichik D, Yurke B (eds) DNA computing and molecular programming. Lecture notes in computer science, vol 8141. Springer, Berlin, pp 90–104CrossRef
go back to reference Hendricks JG, Padilla JE, Patitz MJ, Rogers TA (2013) Signal transmission across tile assemblies: 3D static tiles simulate active self-assembly by 2D signal-passing tiles. Technical report 1306.5005. Computing Research Repository Hendricks JG, Padilla JE, Patitz MJ, Rogers TA (2013) Signal transmission across tile assemblies: 3D static tiles simulate active self-assembly by 2D signal-passing tiles. Technical report 1306.5005. Computing Research Repository
go back to reference Ke Y, Ong LL, Shih WM, Yin P (2012) Three-dimensional structures self-assembled from DNA bricks. Science 338(6111):1177–1183CrossRef Ke Y, Ong LL, Shih WM, Yin P (2012) Three-dimensional structures self-assembled from DNA bricks. Science 338(6111):1177–1183CrossRef
go back to reference Kim J-W, Kim J-H, Deaton R (2011) DNA-linked nanoparticle building blocks for programmable matter. Angew Chem Int Ed 50(39):9185–9190 Kim J-W, Kim J-H, Deaton R (2011) DNA-linked nanoparticle building blocks for programmable matter. Angew Chem Int Ed 50(39):9185–9190
go back to reference Padilla JE, Patitz MJ, Pena R, Schweller RT, Seeman NC, Sheline R, Summers SM, Zhong X (2013) Asynchronous signal passing for tile self-assembly: fuel efficient computation and efficient assembly of shapes. In: Mauri G, Dennunzio A, Manzoni L, Porreca AE (eds) UCNC. Lecture notes in computer science, vol 7956. Springer, Berlin, pp 174–185 Padilla JE, Patitz MJ, Pena R, Schweller RT, Seeman NC, Sheline R, Summers SM, Zhong X (2013) Asynchronous signal passing for tile self-assembly: fuel efficient computation and efficient assembly of shapes. In: Mauri G, Dennunzio A, Manzoni L, Porreca AE (eds) UCNC. Lecture notes in computer science, vol 7956. Springer, Berlin, pp 174–185
go back to reference Pinheiro AV, Han D, Shih WM, Yan H (2011) Challenges and opportunities for structural DNA nanotechnology. Nat Nanotechnol 6(12):763–772 Pinheiro AV, Han D, Shih WM, Yan H (2011) Challenges and opportunities for structural DNA nanotechnology. Nat Nanotechnol 6(12):763–772
go back to reference Rothemund PW, Papadakis N, Winfree E (2004) Algorithmic self-assembly of DNA Sierpinski triangles. PLoS Biol 2(12):e424 Rothemund PW, Papadakis N, Winfree E (2004) Algorithmic self-assembly of DNA Sierpinski triangles. PLoS Biol 2(12):e424
go back to reference Winfree E (1998) Algorithmic self-assembly of DNA. Ph.D. thesis, California Institute of Technology Winfree E (1998) Algorithmic self-assembly of DNA. Ph.D. thesis, California Institute of Technology
go back to reference Woods D, Chen H-L, Goodfriend S, Dabby N, Winfree E, Yin P (2013) Active self-assembly of algorithmic shapes and patterns in polylogarithmic time. In Proceedings of the 4th conference on innovations in theoretical computer science, ITCS ’13. ACM, New York, pp 353–354 Woods D, Chen H-L, Goodfriend S, Dabby N, Winfree E, Yin P (2013) Active self-assembly of algorithmic shapes and patterns in polylogarithmic time. In Proceedings of the 4th conference on innovations in theoretical computer science, ITCS ’13. ACM, New York, pp 353–354
Metadata
Title
Signal transmission across tile assemblies: 3D static tiles simulate active self-assembly by 2D signal-passing tiles
Authors
Tyler Fochtman
Jacob Hendricks
Jennifer E. Padilla
Matthew J. Patitz
Trent A. Rogers
Publication date
01-06-2015
Publisher
Springer Netherlands
Published in
Natural Computing / Issue 2/2015
Print ISSN: 1567-7818
Electronic ISSN: 1572-9796
DOI
https://doi.org/10.1007/s11047-014-9430-0

Other articles of this Issue 2/2015

Natural Computing 2/2015 Go to the issue

Premium Partner