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 prove that there exists a 3D tile set in the 2HAM which is intrinsically universal for the class of all 2D STAM + systems at temperature 1 and 2 (where the 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 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 2 planes of the third dimension.
To achieve this result, we also demonstrate useful techniques and transformations for converting an arbitrarily complex STAM + tile set into an 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 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.
The original version of this chapter was revised: The copyright line was incorrect. This has been corrected. The Erratum to this chapter is available at DOI: 10.1007/978-3-319-01928-4_15
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abel, Z., Benbernou, N., Damian, M., Demaine, E.D., Demaine, M.L., Flatland, R., Kominers, S.D., Schweller, R.T.: Shape replication through self-assembly and rnase enzymes. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1045–1064 (2010)
Becker, F., Rapaport, I., Rémila, É.: Self-assemblying classes of shapes with a minimum number of tiles, and in optimal time. In: Arun-Kumar, S., Garg, N. (eds.) FSTTCS 2006. LNCS, vol. 4337, pp. 45–56. Springer, Heidelberg (2006)
Chandran, H., Gopalkrishnan, N., Reif, J.H.: The tile complexity of linear assemblies. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol. 5555, pp. 235–253. Springer, Heidelberg (2009)
Cheng, Q., Aggarwal, G., Goldwasser, M.H., Kao, M.-Y., Schweller, R.T., de Espanés, P.M.: Complexities for generalized models of self-assembly. SIAM Journal on Computing 34, 1493–1515 (2005)
Costa Santini, C., Bath, J., Tyrrell, A.M., Turberfield, A.J.: A clocked finite state machine built from DNA. Chem. Commun. 49, 237–239 (2013)
Delorme, M., Mazoyer, J., Ollinger, N., Theyssier, G.: Bulking i: An abstract theory of bulking. Theor. Comput. Sci. 412(30), 3866–3880 (2011)
Delorme, M., Mazoyer, J., Ollinger, N., Theyssier, G.: Bulking ii: Classifications of cellular automata. Theor. Comput. Sci. 412(30), 3881–3905 (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. Natural Computing 7(3), 347–370 (2008)
Demaine, E.D., Patitz, M.J., Rogers, T.A., Schweller, R.T., Summers, S.M., Woods, D.: The two-handed tile assembly model is not intrinsically universal. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol. 7965, pp. 400–412. Springer, Heidelberg (2013)
Doty, D., Kari, L., Masson, B.: Negative interactions in irreversible self-assembly. In: Sakakibara, Y., Mi, Y. (eds.) DNA 16. LNCS, vol. 6518, pp. 37–48. Springer, Heidelberg (2011)
Doty, D., Lutz, J.H., Patitz, M.J., Schweller, R.T., Summers, S.M., Woods, D.: 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 (2012)
Fu, B., Patitz, M.J., Schweller, R.T., Sheline, R.: Self-assembly with geometric tiles. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol. 7391, pp. 714–725. Springer, Heidelberg (2012)
Han, D., Pal, S., Yang, Y., Jiang, S., Nangreave, J., Liu, Y., Yan, H.: DNA gridiron nanostructures based on four-arm junctions. Science 339(6126), 1412–1415 (2013)
Hendricks, J.G., Padilla, J.E., Patitz, M.J., Rogers, T.A.: Signal transmission across tile assemblies: 3D static tiles simulate active self-assembly by 2D signal-passing tiles. Technical Report 1306.5005, Computing Research Repository (2013)
Ke, Y., Ong, L.L., Shih, W.M., Yin, P.: Three-dimensional structures self-assembled from dna bricks. Science 338(6111), 1177–1183 (2012)
Kim, J.-W., Kim, J.-H., Deaton, R.: DNA-linked nanoparticle building blocks for programmable matter. Angewandte Chemie International Edition 50(39), 9185–9190 (2011)
Padilla, J.E.: Personal communication (2013)
Padilla, J.E., Patitz, M.J., Pena, R., Schweller, R.T., Seeman, N.C., Sheline, R., Summers, S.M., Zhong, X.: 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)
Pinheiro, A.V., Han, D., Shih, W.M., Yan, H.: Challenges and opportunities for structural dna nanotechnology. Nature Nanotechnology 6(12), 763–772 (2011)
Rothemund, P.W., Papadakis, N., Winfree, E.: Algorithmic self-assembly of dna sierpinski triangles. PLoS Biology 2(12), e424 (2004)
Winfree, E.: Algorithmic Self-Assembly of DNA. PhD thesis, California Institute of Technology (June 1998)
Woods, D., Chen, H.-L., Goodfriend, S., Dabby, N., Winfree, E., Yin, P.: Active self-assembly of algorithmic shapes and patterns in polylogarithmic time. In: Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, ITCS 2013, pp. 353–354. ACM, New York (2013)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hendricks, J., Padilla, J.E., Patitz, M.J., Rogers, T.A. (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. DNA 2013. Lecture Notes in Computer Science, vol 8141. Springer, Cham. https://doi.org/10.1007/978-3-319-01928-4_7
Download citation
DOI: https://doi.org/10.1007/978-3-319-01928-4_7
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-01927-7
Online ISBN: 978-3-319-01928-4
eBook Packages: Computer ScienceComputer Science (R0)