Abstract
Algorithmic self-assembly is the study of the local, distributed, asynchronous algorithms ran by molecules to self-organise, in particular during crystal growth. The general cooperative model, also called “temperature 2”, uses synchronisation to simulate Turing machines, build shapes using the smallest possible amount of tile types, and other algorithmic tasks. However, in the non-cooperative (“temperature 1”) model, the growth process is entirely asynchronous, and mostly relies on geometry. Even though the model looks like a generalisation of finite automata to two dimensions, its 3D generalisation is capable of performing arbitrary (Turing) computation [SODA 2011], and of universal simulations [SODA 2014], whereby a single 3D non-cooperative tileset can simulate the dynamics of all possible 3D non-cooperative systems, up to a constant scaling factor.
However, the original 2D non-cooperative model is not capable of universal simulations [STOC 2017], and the question of its computational power is still widely open and it is conjectured to be weaker than “temperature 2” or its 3D counterpart. Here, we show an unexpected result, namely that this model can reliably grow assemblies of diameter \(\varTheta (n \log n)\) with only n tile types, which is the first asymptotically efficient positive construction.
Research supported by European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 772766, Active-DNA project), and Science Foundation Ireland (SFI) under Grant number 18/ERCS/5746.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Actually, deterministic tile assembly systems map directly to deterministic finite automata.
- 2.
Intuitively, although producible paths are not assemblies, any producible path P encodes an unambiguous description of how to grow \(\mathrm {asm}{(P)}\) from the seed \(\sigma \), according to the order of the sequence P, to produce the assembly \(\sigma \cup \mathrm {asm}{(P)}\).
References
Cannon, S., et al.: Two hands are better than one (up to constant factors). In: STACS: Proceedings of the Thirtieth International Symposium on Theoretical Aspects of Computer Science, pp. 172–184. LIPIcs (2013). arxiv preprint: arXiv:1201.1650
Cook, M., Fu, Y., Schweller, R.T.: Temperature 1 self-assembly: deterministic assembly in 3D and probabilistic assembly in 2D. In: SODA: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 570–589 (2011). arxiv preprint: arXiv:0912.0027
Demaine, E.D., et al.: One tile to rule them all: simulating any tile assembly system with a single universal tile. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 368–379. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-43948-7_31. arxiv preprint: arXiv:1212.4756
Doty, D., Lutz, J.H., Patitz, M.J., Schweller, R.T., Summers, S.M., Woods, D.: The tile assembly model is intrinsically universal. In: FOCS: Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, pp. 439–446. IEEE, October 2012. arxiv preprint: arXiv:1111.3097
Doty, D., Patitz, M.J., Summers, S.M.: Limitations of self-assembly at temperature 1. Theor. Comput. Sci. 412(1–2), 145–158 (2011). arxiv preprint: arXiv:0906.3251
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: SODA: ACM-SIAM Symposium on Discrete Algorithms, pp. 148–167. SIAM (2015). http://arxiv.org/abs/1408.3351
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: Indyk, P. (ed.) Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, 4–6 January 2015, pp. 148–167. SIAM (2015). https://doi.org/10.1137/1.9781611973730.12
Gilbert, O., Hendricks, J., Patitz, M.J., Rogers, T.A.: Computing in continuous space with self-assembling polygonal tiles. In: SODA: ACM-SIAM Symposium on Discrete Algorithms, pp. 937–956. SIAM (2016). arxiv preprint: arXiv:1503.00327
Gilbert, O., Hendricks, J., Patitz, M.J., Rogers, T.A.: Computing in continuous space with self-assembling polygonal tiles (extended abstract). In: Krauthgamer, R. (ed.) Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, 10–12 January 2016, pp. 937–956. SIAM (2016). https://doi.org/10.1137/1.9781611974331.ch67
Hendricks, J., Patitz, M.J., Rogers, T.A., Summers, S.M.: The power of duples (in self-assembly): it’s not so hip to be square. In: Cai, Z., Zelikovsky, A., Bourgeois, A. (eds.) COCOON 2014. LNCS, vol. 8591, pp. 215–226. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-08783-2_19. arxiv preprint: arXiv:1402.4515
Maňuch, J., Stacho, L., Stoll, C.: Two lower bounds for self-assemblies at temperature 1. J. Comput. Biol. 17(6), 841–852 (2010)
Meunier, P.É., Patitz, M.J., Summers, S.M., Theyssier, G., Winslow, A., Woods, D.: Intrinsic universality in tile self-assembly requires cooperation. In: SODA: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pp. 752–771 (2014). arxiv preprint: arXiv:1304.1679
Meunier, P., Woods, D.: The non-cooperative tile assembly model is not intrinsically universal or capable of bounded Turing machine simulation. In: STOC: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 328–341 (2017)
Padilla, J.E., Patitz, M.J., Schweller, R.T., Seeman, N.C., Summers, S.M., Zhong, X.: Asynchronous signal passing for tile self-assembly: fuel efficient computation and efficient assembly of shapes. Int. J. Found. Comput. Sci. 25(4), 459–488 (2014). arxiv preprint: arxiv:1202.5012
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 2011. LNCS, vol. 6937, pp. 175–189. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-23638-9_15. arxiv preprint: arXiv:1105.1215, http://dl.acm.org/citation.cfm?id=2042033.2042050
Rothemund, P.W.K.: Theory and experiments in algorithmic self-assembly. Ph.D. thesis, University of Southern California, December 2001
Rothemund, P.W.K.: Folding DNA to create nanoscale shapes and patterns. Nature 440(7082), 297–302 (2006). https://doi.org/10.1038/nature04586
Rothemund, P.W.K., Winfree, E.: The program-size complexity of self-assembled squares (extended abstract). In: STOC: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pp. 459–468. ACM, Portland (2000). http://doi.acm.org/10.1145/335305.335358
Soloveichik, D., Winfree, E.: Complexity of self-assembled shapes. SIAM J. Comput. 36(6), 1544–1569 (2007)
Thubagere, A.J., et al.: A cargo-sorting DNA robot. Science 357(6356), eaan6558 (2017)
Winfree, E.: Algorithmic self-assembly of DNA. Ph.D. thesis, California Institute of Technology, June 1998
Winfree, E.: Simulations of computing by self-assembly. Technical report, Caltech CS TR:1998.22, California Institute of Technology (1998)
Yurke, B., Turberfield, A.J., Mills, A.P., Simmel, F.C., Neumann, J.L.: A DNA-fuelled molecular machine made of DNA. Nature 406(6796), 605–608 (2000)
Acknowledgments
We would like to thank Damien Woods for invaluable discussions, comments, and suggestions.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
A Make Your Own Large Paths
A Make Your Own Large Paths
A python script is available to generate a 
document with the same kind of terminal assembly as in Fig. 6. For any value of the two integers \(k\ge 1\) and \(n\ge 1\) used in this proof, this script is meant to be called in the following way:
$ python positive.py k n
For example, the drawing in Fig. 6 was produced with:
$ python positive.py 3 10
The script is available on https://github.com/P-E-Meunier/largepaths.
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Meunier, PÉ., Regnault, D. (2019). Non-cooperatively Assembling Large Structures. In: Thachuk, C., Liu, Y. (eds) DNA Computing and Molecular Programming. DNA 2019. Lecture Notes in Computer Science(), vol 11648. Springer, Cham. https://doi.org/10.1007/978-3-030-26807-7_7
Download citation
DOI: https://doi.org/10.1007/978-3-030-26807-7_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-26806-0
Online ISBN: 978-3-030-26807-7
eBook Packages: Computer ScienceComputer Science (R0)