Document Open Access Logo

Universal Shape Replication via Self-Assembly with Signal-Passing Tiles (Extended Abstract)

Authors Andrew Alseth , Daniel Hader, Matthew J. Patitz

PDF
Thumbnail PDF

File

LIPIcs.DNA.28.2.pdf
  • Filesize: 2.26 MB
  • 24 pages

Document Identifiers

Author Details

Andrew Alseth
  • University of Arkansas, Fayetteville, AR, USA
Daniel Hader
  • University of Arkansas, Fayetteville, AR, USA
Matthew J. Patitz
  • University of Arkansas, Fayetteville, AR, USA

Funding

This work was supported in part by NSF grant CAREER-1553166.

Cite AsGet BibTex

Andrew Alseth, Daniel Hader, and Matthew J. Patitz. Universal Shape Replication via Self-Assembly with Signal-Passing Tiles (Extended Abstract). In 28th International Conference on DNA Computing and Molecular Programming (DNA 28). Leibniz International Proceedings in Informatics (LIPIcs), Volume 238, pp. 2:1-2:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.DNA.28.2

Abstract

In this paper, we investigate shape-assembling power of a tile-based model of self-assembly called the Signal-Passing Tile Assembly Model (STAM). In this model, the glues that bind tiles together can be turned on and off by the binding actions of other glues via "signals". In fact, we prove our positive results in a version of the model in which it is slightly more difficult to work (where tiles are allowed to rotate) but show that they also hold in the standard STAM. Specifically, the problem we investigate is "shape replication" wherein, given a set of input assemblies of arbitrary shape, a system must construct an arbitrary number of assemblies with the same shapes and, with the exception of size-bounded junk assemblies that result from the process, no others. We provide the first fully universal shape replication result, namely a single tile set capable of performing shape replication on arbitrary sets of any 3-dimensional shapes without requiring any scaling or pre-encoded information in the input assemblies. Our result requires the input assemblies to be composed of signal-passing tiles whose glues can be deactivated to allow deconstruction of those assemblies, which we also prove is necessary by showing that there are shapes whose geometry cannot be replicated without deconstruction. Additionally, we modularize our construction to create systems capable of creating binary encodings of arbitrary shapes, and building arbitrary shapes from their encodings. Because the STAM is capable of universal computation, this then allows for arbitrary programs to be run within an STAM system, using the shape encodings as input, so that any computable transformation can be performed on the shapes.

Subject Classification

ACM Subject Classification
  • Theory of computation → Models of computation
Keywords
  • Algorithmic self-assembly
  • Tile Assembly Model
  • shape replication

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Zachary Abel, Nadia Benbernou, Mirela Damian, Erik D. Demaine, Martin L. Demaine, Robin Flatland, Scott D. Kominers, and Robert T. Schweller. Shape replication through self-assembly and RNAse enzymes. In SODA 2010: Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1045-1064, Austin, Texas, 2010. Society for Industrial and Applied Mathematics. Google Scholar
  2. Andrew Alseth, Daniel Hader, and Matthew J. Patitz. Self-replication via tile self-assembly. Technical Report 2105.02914, Computing Research Repository, 2021. URL: http://arxiv.org/abs/2105.02914.
  3. Andrew Alseth, Daniel Hader, and Matthew J. Patitz. Self-Replication via Tile Self-Assembly (Extended Abstract). In Matthew R. Lakin and Petr Šulc, editors, 27th International Conference on DNA Computing and Molecular Programming (DNA 27), volume 205 of Leibniz International Proceedings in Informatics (LIPIcs), pages 3:1-3:22, Dagstuhl, Germany, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.DNA.27.3.
  4. Andrew Alseth, Daniel Hader, and Matthew J. Patitz. Universal shape replication via self-assembly with signal-passing tiles, 2022. URL: https://doi.org/10.48550/ARXIV.2206.03908.
  5. Sarah Cannon, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Matthew J. Patitz, Robert T. Schweller, Scott M. Summers, and Andrew Winslow. Two hands are better than one (up to constant factors): Self-assembly in the 2HAM vs. aTAM. In Natacha Portier and Thomas Wilke, editors, STACS, volume 20 of LIPIcs, pages 172-184. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2013. Google Scholar
  6. Cameron Chalk, Erik D. Demaine, Martin L. Demaine, Eric Martinez, Robert Schweller, Luis Vega, and Tim Wylie. Universal shape replicators via Self-Assembly with Attractive and Repulsive Forces. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 225-238. Society for Industrial and Applied Mathematics, January 2017. URL: https://doi.org/10.1137/1.9781611974782.15.
  7. Qi Cheng, Gagan Aggarwal, Michael H. Goldwasser, Ming-Yang Kao, Robert T. Schweller, and Pablo Moisset de Espanés. Complexities for generalized models of self-assembly. SIAM Journal on Computing, 34:1493-1515, 2005. Google Scholar
  8. 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 2014), IT University of Copenhagen, Denmark, July 8-11, 2014, volume 8572 of LNCS, pages 368-379, 2014. Google Scholar
  9. Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Mashhood Ishaque, Eynat Rafalin, Robert T. Schweller, and Diane L. Souvaine. Staged self-assembly: nanomanufacture of arbitrary shapes with O(1) glues. Natural Computing, 7(3):347-370, 2008. URL: https://doi.org/10.1007/s11047-008-9073-0.
  10. Erik D. Demaine, Matthew J. Patitz, Trent A. Rogers, Robert T. Schweller, Scott M. Summers, and Damien Woods. 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, 2013. Google Scholar
  11. Erik D. Demaine, Matthew J. Patitz, Robert T. Schweller, and Scott M. Summers. Self-Assembly of Arbitrary Shapes Using RNAse Enzymes: Meeting the Kolmogorov Bound with Small Scale Factor (extended abstract). In Thomas Schwentick and Christoph Dürr, editors, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011), volume 9 of Leibniz International Proceedings in Informatics (LIPIcs), pages 201-212, Dagstuhl, Germany, 2011. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.STACS.2011.201.
  12. David Doty, Jack H. Lutz, Matthew J. Patitz, Robert T. Schweller, Scott M. Summers, and Damien Woods. The tile assembly model is intrinsically universal. In Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, pages 302-310, 2012. Google Scholar
  13. Jérôme Durand-Lose, Jacob Hendricks, Matthew J. Patitz, Ian Perkins, and Michael Sharp. Self-assembly of 3-D structures using 2-D folding tiles. In David Doty and Hendrik Dietz, editors, DNA Computing and Molecular Programming - 24th International Conference, DNA 24, Jinan, China, October 8-12, 2018, Proceedings, volume 11145 of Lecture Notes in Computer Science, pages 105-121. Springer, 2018. Google Scholar
  14. Constantine Glen Evans. Crystals that count! Physical principles and experimental investigations of DNA tile self-assembly. PhD thesis, California Institute of Technology, 2014. Google Scholar
  15. Tyler Fochtman, Jacob Hendricks, Jennifer E. Padilla, Matthew J. Patitz, and Trent A. Rogers. Signal transmission across tile assemblies: 3D static tiles simulate active self-assembly by 2D signal-passing tiles. Natural Computing, 14(2):251-264, 2015. Google Scholar
  16. Jacob Hendricks, Meagan Olsen, Matthew J. Patitz, Trent A. Rogers, and Hadley Thomas. Hierarchical self-assembly of fractals with signal-passing tiles. Submit to Natrual Computing. Google Scholar
  17. Jacob Hendricks, Matthew J. Patitz, and Trent A. Rogers. Replication of arbitrary hole-free shapes via self-assembly with signal-passing tiles. In Cristian S. Calude and Michael J. Dinneen, editors, Unconventional Computation and Natural Computation - 14th International Conference, UCNC 2015, Auckland, New Zealand, August 30 - September 3, 2015, Proceedings, volume 9252 of Lecture Notes in Computer Science, pages 202-214. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21819-9_15.
  18. Jacob Hendricks, Matthew J. Patitz, and Trent A. Rogers. Universal simulation of directed systems in the abstract tile assembly model requires undirectedness. In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016), New Brunswick, New Jersey, USA October 9-11, 2016, pages 800-809, 2016. Google Scholar
  19. Jacob Hendricks, Matthew J. Patitz, and Trent A. Rogers. Reflections on tiles (in self-assembly). Natural Computing, 16(2):295-316, 2017. URL: https://doi.org/10.1007/s11047-017-9617-2.
  20. Nataša Jonoska and Daria Karpenko. Active tile self-assembly, Part 1: Universality at temperature 1. International Journal of Foundations of Computer Science, 25(02):141-163, 2014. URL: https://doi.org/10.1142/S0129054114500087.
  21. Nataša Jonoska and Daria Karpenko. Active tile self-assembly, Part 2: Self-similar structures and structural recursion. International Journal of Foundations of Computer Science, 25(02):165-194, 2014. URL: https://doi.org/10.1142/S0129054114500099.
  22. Yonggang Ke, Luvena L Ong, William M Shih, and Peng Yin. Three-dimensional structures self-assembled from DNA bricks. Science, 338(6111):1177-1183, 2012. Google Scholar
  23. Alexandra Keenan, Robert T. Schweller, and Xingsi Zhong. Exponential replication of patterns in the signal tile assembly model. In David Soloveichik and Bernard Yurke, editors, DNA, volume 8141 of Lecture Notes in Computer Science, pages 118-132. Springer, 2013. URL: https://doi.org/10.1007/978-3-319-01928-4_9.
  24. James I. Lathrop, Jack H. Lutz, Matthew J. Patitz, and Scott M. Summers. Computability and complexity in self-assembly. Theory Comput. Syst., 48(3):617-647, 2011. URL: https://doi.org/10.1007/s00224-010-9252-0.
  25. James I. Lathrop, Jack H. Lutz, and Scott M. Summers. Strict self-assembly of discrete Sierpinski triangles. Theoretical Computer Science, 410:384-405, 2009. Google Scholar
  26. Austin Luchsinger, Robert Schweller, and Tim Wylie. Self-assembly of shapes at constant scale using repulsive forces. Natural Computing, August 2018. URL: https://doi.org/10.1007/s11047-018-9707-9.
  27. Pierre-Étienne Meunier, Damien Regnault, and Damien Woods. The program-size complexity of self-assembled paths. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 727-737. ACM, 2020. URL: https://doi.org/10.1145/3357713.3384263.
  28. Jennifer E. Padilla, Matthew J. Patitz, Robert T. Schweller, Nadrian C. Seeman, Scott M. Summers, and Xingsi Zhong. Asynchronous signal passing for tile self-assembly: Fuel efficient computation and efficient assembly of shapes. International Journal of Foundations of Computer Science, 25(4):459-488, 2014. Google Scholar
  29. Matthew J. Patitz, Robert T. Schweller, and Scott M. Summers. Exact shapes and Turing universality at temperature 1 with a single negative glue. In Luca Cardelli and William M. Shih, editors, DNA Computing and Molecular Programming - 17th International Conference, DNA 17, Pasadena, CA, USA, September 19-23, 2011. Proceedings, volume 6937 of Lecture Notes in Computer Science, pages 175-189. Springer, 2011. Google Scholar
  30. Matthew J. Patitz and Scott M. Summers. Self-assembly of decidable sets. Natural Computing, 10(2):853-877, 2011. URL: https://doi.org/10.1007/s11047-010-9218-9.
  31. Matthew J. Patitz and Scott M. Summers. Identifying shapes using self-assembly. Algorithmica, 64(3):481-510, 2012. Google Scholar
  32. Paul W. K. Rothemund and Erik Winfree. The program-size complexity of self-assembled squares (extended abstract). In STOC '00: Proceedings of the thirty-second annual ACM Symposium on Theory of Computing, pages 459-468, Portland, Oregon, United States, 2000. ACM. Google Scholar
  33. Rebecca Schulman, Bernard Yurke, and Erik Winfree. Robust self-replication of combinatorial information via crystal growth and scission. Proceedings of the National Academy of Sciences, 109(17):6405-10, 2012. URL: http://www.biomedsearch.com/nih/Robust-self-replication-combinatorial-information/22493232.html.
  34. David Soloveichik and Erik Winfree. Complexity of self-assembled shapes. SIAM Journal on Computing, 36(6):1544-1569, 2007. URL: https://doi.org/10.1137/S0097539704446712.
  35. Scott M. Summers. Reducing tile complexity for the self-assembly of scaled shapes through temperature programming. Algorithmica, 63(1-2):117-136, June 2012. URL: https://doi.org/10.1007/s00453-011-9522-5.
  36. Erik Winfree. Algorithmic Self-Assembly of DNA. PhD thesis, California Institute of Technology, June 1998. Google Scholar
  37. Damien Woods, David Doty, Cameron Myhrvold, Joy Hui, Felix Zhou, Peng Yin, and Erik Winfree. Diverse and robust molecular algorithms using reprogrammable DNA self-assembly. Nature, 567:366-372, 2019. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact