Hierarchical self assembly of patterns from the Robinson tilings: DNA tile design in an enhanced Tile Assembly Model | Natural Computing Skip to main content
Springer Nature Link
Log in

Hierarchical self assembly of patterns from the Robinson tilings: DNA tile design in an enhanced Tile Assembly Model

  • Published:
Natural Computing Aims and scope Submit manuscript

Abstract

We introduce a hierarchical self assembly algorithm that produces the quasiperiodic patterns found in the Robinson tilings and suggest a practical implementation of this algorithm using DNA origami tiles. We modify the abstract Tile Assembly Model (aTAM), to include active signaling and glue activation in response to signals to coordinate the hierarchical assembly of Robinson patterns of arbitrary size from a small set of tiles according to the tile substitution algorithm that generates them. Enabling coordinated hierarchical assembly in the aTAM makes possible the efficient encoding of the recursive process of tile substitution.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  • Abel Z, Benbernou N, Damian M, Demaine E, Demaine M, 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, Philadelphia, pp 1045–1064

  • Adleman LM (2000) Towards a mathematical theory of self-assembly. Computer Science Technical Report 00-722, University of Southern California

  • Adleman L, Cheng Q, Goel A, Huang M-D, Kempe D, de Espanés PM, Rothemund PWK (2002) Combinatorial optimization problems in self-assembly. In: Proceedings of the thirty-fourth annual ACM symposium on theory of computing, Montréal, QC, Canada, pp 23–32

  • 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

    Article  MathSciNet  MATH  Google Scholar 

  • Birac JJ, Sherman WB, Kopatsch J, Constantinou PE, Seeman NC (2006) Architecture with GIDEON, a program for design in structural DNA nanotechnology. J Mol Graph Model 25(4):470–480

    Article  Google Scholar 

  • Carbone A, Seeman NC (2004) Molecular tiling and DNA self-assembly. In: Aspects of molecular computing. LNCS, vol 2950. Springer, New York, pp 61–83

  • Chen H-L, Doty D (2011) Parallelism and time in hierarchical self-assembly. arXiv:1104.5226v1

  • Cheng Q, Goel A, de Espanés PM (2004) Optimal self-assembly of counters at temperature two. In: Proceedings of the first conference on foundations of nanoscience: self-assembled architectures and devices, Snowbird, UT

  • Choi HMT, Chang JY, Trinh LA, Padilla JE, Fraser SE, Pierce NA (2010) Programmable in situ amplification for multiplexed imaging of mRNA expression. Nat Biotechnol 28(11):1208–1212

    Article  Google Scholar 

  • 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

    Article  MathSciNet  MATH  Google Scholar 

  • Demaine ED, Patitz M, Schweller R, Summers S (2011) Self-assembly of arbitrary shapes using RNAse enzymes: meeting the Kolmogorov bound with small scale factor. In: Schwentick T, Dürr C (eds) STACS 2011: proceedings of the 28th international symposium on theoretical aspects of computer science, Dortmund, Germany, pp 201–212

  • Dirks RM, Pierce NA (2004) Triggered amplification by hybridization chain reaction. Proc Natl Acad Sci USA 101(43):15275–15278

    Article  Google Scholar 

  • Doty D, Lutz JH, Patitz MJ, Summers SM, Woods D (2009) Intrinsic universality in self-assembly. In: Proceedings of the 27th international symposium on theoretical aspects of computer science, Nancy, France

  • 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, Nevada, USA, pp 417–426

  • Doty D, Kari L, Masson B (2011) Negative interactions in irreversible self-assembly. In: Sakakibara Y, Mi Y (eds) DNA computing and molecular programming. Lecture Notes in Computer Science, vol 6518. Springer, Berlin, Heidelberg, pp 37–48

  • Durand B (1999) Tilings and quasiperiodicity. Theor Comput Sci 221:61–75

    Article  MathSciNet  MATH  Google Scholar 

  • Frank NP (2008) A primer of substitution tilings of the euclidean plane. Expo Math 26(4):295–326

    Article  MathSciNet  MATH  Google Scholar 

  • Goodman-Strauss C (1999) Aperiodic hierarchical tilings. In: Foams, emulsions, and cellular materials (Cargèse, 1997). NATO advanced science institutes series E: applied sciences, vol 354. Kluwer, Dordrecht, pp 481–496

  • Grünbaum B, Shephard GC (1987) Tilings and patterns. Freeman, New York

    MATH  Google Scholar 

  • Lafitte G, Weiss M (2008a) Computability of tilings. In: Fifth IFIP international conference on theoretical computer science-TCS 2008: IFIP 20th World Computer Congress, TC 1, Foundations of Computer Science, September 7–10, 2008, Milano, Italy, pp 187–201

  • Lafitte G, Weiss M (2008b) Simulations between tilings. In: Beckmann A, Dimitracopoulos C, Löwe B (eds) Fourth conference on computability in Europe, CiE 2008. Logic and theory of algorithms, p 264

  • Lathrop JI, Lutz JH, Patitz MJ, Summers SM (2008) Computability and complexity in selfassembly. In: Beckmann A, Dimitracopoulos C, Löwe B (eds) Logic and theory of algorithms. Lecture Notes in Computer Science, vol 5028. Springer, Berlin, Heidelberg, pp 349–358

  • Liu F, Sha R, Seeman NC (1999) Modifying the surface features of two-dimensional DNA crystals. J Am Chem Soc 121(5):917–922

    Article  Google Scholar 

  • Liu W, Zhong H, Wang R, Seeman NC (2011) Crystalline two-dimensional DNA origami arrays. Angew Chem 50(1):264–267

    Article  Google Scholar 

  • Lund K, Manzo AJ, Dabby N, Michelotti N, Johnson-Buck A, Nangreave J, Taylor S, Pei R, Stojanovic MN, Walter NG, Winfree E, Yan H (2010) Molecular robots guided by prescriptive landscapes. Nature 465(7295):206–210

    Article  Google Scholar 

  • Majumder U, LaBean TH, Reif JH (2008) Activatable tiles: compact, robust programmable assembly and other applications. In: Garzon MH, Yan H (eds) DNA computing. LNCS 4848, pp 15–25

  • Mao C, LaBean TH, Reif JH, Seeman NC (2000) Logical computation using algorithmic self-assembly of DNA triple-crossover molecules. Nature 407(6803):493–496

    Google Scholar 

  • Nanorex Inc (2008) Nanoengineer-1, version 1.1.1. http://www.nanoengineer-1.com/

  • Omabegho T, Sha R, Seeman NC (2009) A bipedal DNA Brownian motor with coordinated legs. Science 324(5923):67

    Article  Google Scholar 

  • Patitz MJ, Summers SM (2008) Selfassembly of decidable sets. In: Calude CS, Costa JF, Freund R, Rozenberg G (eds) Proceedings of the seventh international conference on unconventional computation, Vienna, Austria. Lecture Notes in Computer Science, vol 5204. Springer-Verlag, Berlin, Heidelberg, pp 206–219

  • Patitz MJ, Summers SM (2010) Identifying shapes using self-assembly. In: Cheong et al (eds) Algorithms and computation. LNCS 6507, pp 458–469

  • Penrose R (1974) The role of aesthetics in pure and applied mathematical research. Bull Inst Math Appl 10(7/8):266–271

    Google Scholar 

  • Penrose R (1979) Pentaplexity a class of non-periodic tilings of the plane. Math Intell 2(1):32–37

    Article  MathSciNet  MATH  Google Scholar 

  • Qian L, Winfree E (2009) A simple DNA gate motif for synthesizing large-scale circuits. In: Goel A, Simmel FC, Sosik P (eds) DNA computing. Lecture Notes in Computer Science, vol 5347. Springer-Verlag, Berlin, Heidelberg, pp 70–89

  • Reif JH, Sahu SE, Yin P (2006) Complexity of graph self-assembly in accretive systems and self-destructible systems. In: Carbone A, Pierce NA (eds) DNA computing. Lecture Notes in Computer Science, vol 3892. Springer-Verlag, Berlin, Heidelberg, pp 257–274

  • Robinson RM (1971) Undecidability and nonperiodicity for tilings of the plane. Invent Math 12(3):177–209

    Article  MathSciNet  Google Scholar 

  • Rothemund PWK (2000) Using lateral capillary forces to compute by self-assembly. Proc Natl Acad Sci USA 97(3):984–989

    Article  Google Scholar 

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

  • Rothemund PWK (2006) Folding DNA to create nanoscale shapes and patterns. Nature 440(7082):297–302

    Article  Google Scholar 

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

  • Rothemund PWK, Papadakis N, Winfree E (2004) Algorithmic self-assembly of DNA Sierpinski triangles. PLoS Biol 2(12):e424

    Article  Google Scholar 

  • Schrödinger, LLC (2010) The PyMOL molecular graphics system, 870 version 1.3r1. http://pymol.org/

  • Seelig G, Soloveichik D, Zhang DY, Winfree E (2006a) Enzyme-free nucleic acid logic circuits. Science 314(5805):1585–1588

    Article  Google Scholar 

  • Seelig G, Yurke B, Winfree E (2006b) Catalyzed relaxation of a metastable DNA fuel. J Am Chem Soc 128(37):12211–12220

    Article  Google Scholar 

  • Seeman NC (1990) De novo design of sequences for nucleic acid structure engineering. J Biomol Struct Dyn 8(3):573-581

    Google Scholar 

  • Senechal M (1996) Quasicrystals and geometry. Cambridge University Press, Cambridge

    Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  • Spicher A, Michel O, Giavitto J-L (2006) Algorithmic self-assembly by accretion and by carving in MGS. In: Talbi E-G, Liardet P, Collet P, Lutton E, Schoenauer M (eds) Artificial evolution. Lecture Notes in Computer Science, vol 3871. Springer-Verlag, Berlin, Heidelberg, pp 189–200

  • Turberfield AJ, Mitchell JC, Yurke B, Mills AP, Blakey MI, Simmel FC (2003) DNA fuel for free-running nanomachines. Phys Rev Lett 90(11):118102-1–118102-4

    Article  Google Scholar 

  • Wang H (1961) Proving theorems by pattern recognition II. AT&T Bell Lab Tech J 40:1–41

    Google Scholar 

  • Wang R, Kuzuya A, Liu W, Seeman NC (2010) Blunt-ended DNA stacking interactions in a 3-helix motif. Chem Comm 46:4905–4907

    Google Scholar 

  • Wickham SFJ, Endo M, Katsuda Y, Hikada K, Bath J, Sugiyama H, Turberfield AJ (2011) Direct observation of stepwise movement of a synthetic molecular transporter. Nat Nanotechnol 6(3):166–169

    Article  Google Scholar 

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

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

    Chapter  Google Scholar 

  • Yin P, Choi HMT, Calvert CR, Pierce NA (2008) Programming biomolecular self-assembly pathways. Nature 451(7176):318–322

    Article  Google Scholar 

  • Yurke B, Turberfield AJ, Mills AP, Simmel FC, Neumann JL (2000) A DNA-fuelled molecular machine made of DNA. Nature 406(6796):605–608

    Article  Google Scholar 

  • Zadeh JN, Steenberg CD, Bois JS, Wolfe BR, Pierce MB, Khan AR, Dirks RM, Pierce NA (2011) NUPACK: analysis and design of nucleic acid systems. J Comput Chem 32(1):170–173

    Article  Google Scholar 

  • Zhang DY, Turberfield AJ, Yurke B, Winfree E (2007) Engineering entropy-driven reactions and networks catalyzed by DNA. Science 318(5853):1121–1125

    Article  Google Scholar 

  • Zheng J, Birktoft JJ, Chen Y, Wang T, Sha R, Constantinou PE, Ginell SL, Mao C, Seeman NC (2009) From molecular to macroscopic via the rational design of a self-assembled 3D DNA crystal. Nature 461(7260):74–77

    Article  Google Scholar 

Download references

Acknowledgments

We thank Natasha Jonoska for helpful discussions and anonymous reviewers for helpful suggestions. This research has been supported by the following grants to NCS: GM-29554 from the National Institute of General Medical Sciences, CTS-0608889 and CCF-0726378 from the National Science Foundation, W911NF-11-1-0024 and W911NF-07-1-0439 from the Army Research Office, N000140910181 and N000140911118 from the Office of Naval Research and a grant from the W.M. Keck Foundation.

Author information

Authors and Affiliations

  1. Monrovia, CA, 91016, USA

    Jennifer E. Padilla

  2. Department of Chemistry, New York University, New York, NY, 10003, USA

    Wenyan Liu & Nadrian C. Seeman

Authors
  1. Jennifer E. Padilla
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Wenyan Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Nadrian C. Seeman
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jennifer E. Padilla.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Padilla, J.E., Liu, W. & Seeman, N.C. Hierarchical self assembly of patterns from the Robinson tilings: DNA tile design in an enhanced Tile Assembly Model. Nat Comput 11, 323–338 (2012). https://doi.org/10.1007/s11047-011-9268-7

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11047-011-9268-7

Keywords

Search

Navigation