# A Brief Tour of Theoretical Tile Self-Assembly

Andrew Winslow

► To cite this version:

Andrew Winslow. A Brief Tour of Theoretical Tile Self-Assembly. 22th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2016, Zurich, Switzerland. pp.26-31, 10.1007/978-3-319-39300-1_3. hal-01435031

HAL Id: hal-01435031

https://inria.hal.science/hal-01435031

Submitted on 13 Jan 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
A Brief Tour of Theoretical Tile Self-Assembly

Andrew Winslow<fnref n="1" />

Université Libre de Bruxelles, Brussels, Belgium
awinslow@ulb.ac.be

**Abstract.** The author gives a brief historical tour of theoretical tile self-assembly via chronological sequence of reports on selected topics in the field. The result is to provide context and motivation for the these results and the field more broadly.

**Introduction.** This tour covers only a subset of the research topics in the-oretical tile self-assembly. It is intended for readers who are familiar with the basics of the field and wish to obtain a better understanding of how the mul-titude of models, problems, and results relate. As such, it is neither a survey nor an introduction; for these, the reader is referred to the excellent works of Doty [18], Patitz [37], Woods [50], and Winfree [47]. Moreover, it does not cover work in experimental DNA tile self-assembly.

**The aTAM of Winfree (1990s).** It is common for work on theoretical tile self-assembly (hereafter *tile assembly*), to begin “In his Ph.D. thesis, Winfree [47] introduced the *abstract tile assembly model (aTAM)* ...”. The ubiquity of this opener matches the importance this work plays in the field: it is the point of conception, and nearly 20 years later, its reading connotes initiation to the area. Moreover, the sustained popularity of tile assembly is due in large part to the elegance and hidden intricacy of this original model. Such intricacy is perhaps most crystallized in a simple yet devious question: is universal computation possible in the aTAM at temperature 1?

As with any research, the concept of the aTAM and its experimental im-plementations were not in isolation. Several other models of (linear) DNA-based computation also introduced around this time, including the filtering-based mod-els of Adleman [2] and Beaver [8] and the splicing systems of Pâun, Kari, Yoko-mori, and others [27,39,51].

**Benchmark Problems (2000-2004).** Beyond defining the aTAM, the Win-free thesis also contains a proof of the computational universality of the aTAM at temperature 2. This result established algorithmic universality, but not the ability to assemble shapes *efficiently*, i.e., using systems of few tile types. Rothe-mund and Winfree [41] soon established this, achieving $n \times n$ square assembly with $O(\log n)$ tile types. Following this work, the twin capabilities of universal computation and efficient square assembly became the de facto benchmarks for powerful models of tile assembly.<fnref n="1" />

<footnote n="1">¹ As discussed later, these simple challenges ultimately proved insufficient detailed for distinguishing between some powerful but unequal models.</footnote>
Followup work by Adleman et al. [4,13] closed the small gaps in optimality left by the construction Rothemund and Winfree and introduced a new metric of efficiency: (expected) assembly time. This metric was ported from simultaneous work on the dynamics of linear assemblies by Adleman et al. [3,6] and considered in other models later [10]. Shortly after, efficient assembly of general (non-square) shapes was proved NP-complete by Adleman et al. [5], while Soloveichik and Winfree [45] established the *geometric universality* [46] of the aTAM: the construction of all shapes efficiently (if scaling is permitted).

Even beyond techniques for information encoding and construction analysis introduced in [4,45], perhaps the most persistent single contribution of work in this era was implicit conjecture in [41] that the aTAM at temperature 1 is not capable of (universal) computation, based on related conjectured lower bound of $2n - 1$ tiles to assemble $n \times n$ squares.

**Error-Prone Models (2002-2011).** Some of the earliest variations on the aTAM were those concerned with the design of systems robust to various errors in the assembly process. Such errors included incorrect tile attachments [11,12,42,44,49], assembly “damage” via partial deletion [44,48], temperature fluctuations [24], and unseeded growth [43]. In an ironic turn, the adversarial “seedless” growth addressed by Schulman et al. [43] was later used to achieve efficient constructions impossible with seeded growth [9]. The collection of error-prone models and results demonstrated that even small changes to aTAM yield rich new ideas. New model variations remain the largest catalyst of new work in tile assembly.

**The Temperature 1 Problem (2005-ongoing).** The *Temperature-1 Problem* is the most notorious open problem in tile assembly: is the temperature-1 aTAM computationally universal? The widely conjectured answer is a resounding “Obviously not!”<fnref n="2" />, but the problem has resisted nearly all progress, permitting only negative results that use either stronger conjectures [33,34], weaker models [32,40], or the assumption of other plausible conjectures [25].

One primary difficulty is even obtaining a precise formal statement of what constitutes “computation” in tile assembly. The second is developing a proof approach that passes the “3D test”: the proof must break in 3D, implied by the result of Cook, Fu, and Schweller [14].

**Computational Universality via Weak Cooperation (2007-2012).** The computationally universality of the aTAM at temperature 2 and the temperature 1 problem beg the question of whether computational universality can be achieved by adding other features to the temperature-1 aTAM. Several variations of the temperature-1 aTAM were considered for which the answer proved to be “Yes”. These included models using the third dimension [14], negative-strength glues [21,38], non-square tiles [26,29], and tiles with triggerable “signals” [30,36]. These models commonly exploit either “weak cooperation” in the form of repelling forces or the ability to “jump over walls”.

**Handedness (2008-2014)** In addition to models adding features to the temperature-1 aTAM, other modifications to the aTAM were under consider-

<footnote n="2">² Usually accompanied by an exaggerated shoulder shrug and waving, upturned palms.</footnote>
ation. In particular, the elimination of the seed was considered in the *hier-
archical* or *two-handed (2HAM)* tile assembly models, hinted at in several set-
tings [7,15,31] before reaching the formulation used currently [1,24]. Surprisingly,
the removal of the seed causes numerous unexpected effects, including increased
power [9], runaway growth [19,20], and no improvement in assembly time [10].

**Intrinsic Universality (2010-present).** By 2010, the introduction of new tile assembly models was occurring regularly. As previously described, many of these models obtained computational universality, but through alternative “weakly cooperative” means. With a few exceptions where direct simulation was possible (e.g., 2HAM simulation of aTAM [9]), the understanding of the relative power of these models was unsatisfyingly coarse: models are either computation-ally universal or not.

Adapting definitions of a geometric notion of simulation from cellular au-
tomata (see [28,35]), Doty et al. [22,23] established that the temperature-2 aTAM
is *intrinsic universal* for all aTAM systems: there exists a single temperature-2
tile set that simulates the behavior of any aTAM system (when provided with a
seed assembly encoding the system). Subsequent work used this new comparative
metric to prove positive and negative intrinsic universality results for variations
of the 2HAM, aTAM, and polygonal tile model [16,17,29,34]. In progress to-
wards the Temperature 1 Problem, the temperature-1 aTAM was proved not
intrinsically universal for the higher temperature aTAM [34], failing to match
temperature 2.

References

1. Z. Abel, N. Benbernou, M. Damian, E. D. Demaine, M. L. Demaine, R. Flatland, S. D. Kominers, and R. Schweller. Shape replication through self-assembly and RNase enzymes. In *Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA)*, 2010.

2. L. Adleman. Molecular computation of solutions to combinatorial problems. *Nature*, 266(5187):1021–1024, 1994.

3. L. Adleman. Toward a mathematical theory of self-assembly (extended abstract). Technical Report 00-722, University of Southern California, 2000.

4. L. Adleman, Q. Cheng, A. Goel, and M.-D. Huang. Running time and program size for self-assembled squares. In *Proceedings of Symposium on Theory of Computing (STOC)*, 2001.

5. L. Adleman, Q. Cheng, A. Goel, M.-D. Huang, D. Kempe, P. M. de Espanés, and P. W. K. Rothemund. Combinatorial optimization problems in self-assembly. In *Proceedings of Symposium on Theory of Computing (STOC)*, 2002.

6. L. M. Adleman, Q. Cheng, A. Goel, M.-D. Huang, and H. Wasserman. Linear self-assemblies: Equilibria, entropy and convergence rates. In B. Aulbach, S. N. Elaydi, and G. Ladas, editors, *Proceedings of Sixth International Conference on Difference Equations and Applications*, 2001.

7. G. Aggarwal, Q. Cheng, M. Goldwasser, M. Kao, P. de Espanes, and R. Schweller. Complexities for generalized models of self-assembly. *SIAM Journal on Computing*, 34(6):1493–1515, 2005.

8. D. Beaver. A universal molecular computer. In *DNA Based Computers: Proceedings of a DIMACS Workshop*, pages 29–36. American Mathematical Society, 1996.
9. S. Cannon, E. D. Demaine, M. L. Demaine, S. Eisenstat, M. J. Patitz, R. T. Schweller, S. M. Summers, and A. Winslow. Two hands are better than one (up to constant factors): Self-assembly in the 2HAM vs. aTAM. In *Proceedings of International Symposium on Theoretical Aspects of Computer Science (STACS)*, volume 20 of *LIPIcs*, pages 172–184. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2013.

10. H. Chen and D. Doty. Parallelism and time in hierarchical self-assembly. In *ACM-SIAM Symposium on Discrete Algorithms*, 2012.

11. H.-L. Chen, Q. Cheng, A. Goel, M.-D. Huang, and P. M. de Espanés. Invadable self-assembly: combining robustness with efficiency. In *Proceedings of the 15th Annual Symposium on Discrete Algorithms (SODA)*, pages 890–899, 2004.

12. H.-L. Chen and A. Goel. Error free self-assembly using error prone tiles. In *Proceedings of 10th International Workshop on DNA Computing (DNA)*, volume 3384 of *LNCS*, pages 62–75. Springer, 2005.

13. Q. Cheng, A. Goel, and P. Moisset. Optimal self-assembly of counters at temperature two. In *Proceedings of the 1st Conference on Foundations of nanoscience: self-assembled architectures and devices*, 2004.

14. M. Cook, Y. Fu, and R. Schweller. Temperature 1 self-assembly: deterministic assembly in 3d and probabilistic assembly in 2d. In *ACM-SIAM Symposium on Discrete Algorithms (SODA)*, 2011.

15. E. D. Demaine, M. L. Demaine, S. P. Fekete, M. Ishaque, E. Rafalin, R. T. Schweller, and D. L. Souvaine. Staged self-assembly: nanomanufacture of arbitrary shapes with $O(1)$ glues. *Natural Computing*, 7(3):347–370, 2008.

16. E. D. Demaine, M. L. Demaine, S. P. Fekete, M. J. Patitz, R. T. Schweller, A. Winslow, and D. Woods. One tile to rule them all: Simulating any tile assembly system with a single universal tile. In *Proceedings of the 41st International Colloquium on Automata, Languages, and Programming (ICALP)*, volume 8572 of *LNCS*, pages 368–379. Springer, 2014.

17. E. D. Demaine, M. J. Patitz, T. A. Rogers, R. T. Schweller, and D. Woods. The two-handed tile assembly model is not intrinsically universal. In *Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP)*, volume 7965 of *LNCS*, pages 400–412. Springer, 2013.

18. D. Doty. Theory of algorithmic self-assembly. *Communications of the ACM*, 55(12):78–88, 2012.

19. D. Doty. Producibility in hierarchical self-assembly. In *Proceedings of Unconventional Computation and Natural Computation (UCNC)*, volume 8553 of *LNCS*, pages 142–154. Springer, 2014.

20. D. Doty. Pattern overlap implies runaway growth in hierarchical tile systems. *Journal of Computational Geometry*, 7(2):3–18, 2016.

21. D. Doty, L. Kari, and B. Masson. Negative interactions in irreversible self-assembly. *Algorithmica*, 66(1):153–172, 2013.

22. D. Doty, J. H. Lutz, M. J. Patitz, R. T. Schweller, S. M. Summers, and D. Woods. The tile assembly model is intrinsically universal. In *Proceedings of the 53rd Annual Symposium on Foundations of Computer Science (FOCS)*, pages 302–310, 2012.

23. D. Doty, J. H. Lutz, M. J. Patitz, S. M. Summers, and D. Woods. Intrinsic universality in self-assembly. In *Proceedings of International Symposium on Theoretical Aspects of Computer Science (STACS)*, volume 5 of *LIPIcs*, pages 275–286. Schloss Dagstuhl, 2010.

24. D. Doty, M. J. Patitz, D. Reishus, R. T. Schweller, and S. M. Summers. Strong fault-tolerance for self-assembly with fuzzy temperature. In *Foundations of Computer Science (FOCS)*, pages 417–426, 2010.
25. D. Doty, M. J. Patitz, and S. M. Summers. Limitations of self-assembly at temperature one. In *Proceedings of 15th International Conference on DNA Computing and Molecular Programming (DNA)*, volume 5877 of LNCS, pages 35–44. Springer, 2009.

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

27. R. Freund, L. Kari, and G. Pàun. Dna computing based on splicing: the existence of universal computers. *Theory of Computing Systems*, 32(69–112), 1999.

28. E. Goles, P.-E. Meunier, I. Rappaport, and G. Theyssier. Communication complexity and intrinsic universality in cellular automata. *Theoretical Computer Science*, 412(1–2):2–21, 2011.

29. J. Hendricks, M. J. Patitz, and T. A. Rogers. The simulation powers and limitations of higher temperature hierarchical self-assembly systems. Technical report, arXiv, 2015.

30. N. Jonoska and D. Karpenko. Active tile self-assembly, part 1: universality at temperature 1. *International Journal of Foundations of Computer Science*, 25(2):141–163, 2014.

31. C. Luhrs. Polyomino-safe DNA self-assembly via block replacement. *Natural Computing*, 9(1):97–109, 2010.

32. J. Mañuch, L. Stacho, and C. Stoll. Journal of computational biology. *Journal of Computational Biology*, 16(6):841–852, 2010.

33. P.-E. Meunier. The self-assembly of paths and squares at temperature 1. Technical report, arXiv, 2013.

34. P.-E. Meunier, M. J. Patitz, S. M. Summers, G. Theyssier, A. Winslow, and D. Woods. Intrinsic universality in tile self-assembly requires cooperation. In *Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)*, pages 752–771, 2014.

35. N. Ollinger. Universalities in cellular automata. In G. Rozenberg, T. Bäck, and J. N. Kok, editors, *Handbook of Natural Computing*, pages 190–229. Springer, 2012.

36. J. E. Padilla, M. J. Patitz, R. Pena, R. T. Schweller, N. C. Seeman, R. Sheline, S. M. Summers, and X. Zhong. Asynchronous signal passing for tile self-assembly: Fuel efficient computation and efficient assembly of shapes. In *Proceedings of the 12th International Conference on Unconventional Computation and Natural Computation (UCNC)*, pages 174–185, 2013.

37. M. J. Patitz. An introduction to tile-based self-assembly. In J. Durand-Lose and N. Jonoska, editors, *UCNC 2012*, volume 7445 of LNCS, pages 34–62. Springer Berlin Heidelberg, 2012.

38. M. J. Patitz, R. T. Schweller, and S. M. Summers. Exact shapes and turing universality at temperature 1 with a single negative glue. In *Proceedings of the 17th International Conference on DNA Computing and Molecular Programming (DNA)*, volume 6937 of LNCS, pages 175–189. Springer, 2011.

39. G. Pàun. On the power of the splicing operation. *International Journal of Computer Mathematics*, 59(1–2):27–35, 1995.

40. J. Reif and T. Song. The computation complexity of temperature-1 tilings. Technical report, Duke University, 2014.

41. P. W. K. Rothemund and E. Winfree. The program-size complexity of self-assembled squares. In *Proceedings of ACM Symposium on Theory of Computing (STOC)*, pages 459–468, 2000.
42. S. Sahu and J. Reif. Capabilities and limits of compact error resilience methods for algorithmic self-assembly in two and three dimensions. In *Proceedings of the 12th International Meeting on DNA Computing*, volume 4287 of LNCS, pages 223–238. Springer, 2006.

43. R. Schulman and E. Winfree. Programmable control of nucleation for algorithmic self-assembly. *SIAM Journal on Computing*, 39(4):1581–1616, 2009.

44. D. Soloveichik, M. Cook, and E. Winfree. Combining self-healing and proofreading in self-assembly. *Natural Computing*, 7(2):203–218, 2008.

45. D. Soloveichik and E. Winfree. Complexity of self-assembled shapes (extended abstract). In *Proceedings of 10th International Workshop on DNA Computing*, volume 3384 of LNCS, pages 344–354. Springer, 2005.

46. S. M. Summers. *Universality in algorithm self-assembly*. PhD thesis, Iowa State University, 2010.

47. E. Winfree. *Algorithmic Self-Assembly of DNA*. PhD thesis, Caltech, 1998.

48. E. Winfree. Self-healing tile sets. In *Nanotechnology: Science and Computation*, pages 55–78. Springer, 2006.

49. E. Winfree and R. Bekbolatov. Proofreading tile sets: Error correction for algorithmic self-assembly. In *Proceedings of the 9th International Workshop on DNA Based Computers (DNA)*, volume 2943 of LNCS, pages 126–144. Springer, 2004.

50. D. Woods. Intrinsic universality and the computational power of self-assembly. *Philosophical Transaction of the Royal Society A*, 373(2046), 2015.

51. T. Yokomori and S. Kobayashi. Dna-ec: a model of dna computing based on equality checking. In *DNA Based Computers III*, volume 48 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 347–359. American Mathematical Society, 1999.