Document Open Access Logo

Self-Replication via Tile Self-Assembly (Extended Abstract)

Authors Andrew Alseth , Daniel Hader, Matthew J. Patitz

PDF
Thumbnail PDF

File

LIPIcs.DNA.27.3.pdf
  • Filesize: 3.53 MB
  • 22 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

  • Alseth, Andrew: This author’s work was supported in part by NSF grant CAREER-1553166.
  • Hader, Daniel: This author’s work was supported in part by NSF grant CAREER-1553166.
  • Patitz, Matthew J.: This author’s work was supported in part by NSF grant CAREER-1553166.

Cite As Get BibTex

Andrew Alseth, Daniel Hader, and Matthew J. Patitz. Self-Replication via Tile Self-Assembly (Extended Abstract). In 27th International Conference on DNA Computing and Molecular Programming (DNA 27). Leibniz International Proceedings in Informatics (LIPIcs), Volume 205, pp. 3:1-3:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.DNA.27.3

Abstract

In this paper we present a model containing modifications to the Signal-passing Tile Assembly Model (STAM), a tile-based self-assembly model whose tiles are capable of activating and deactivating glues based on the binding of other glues. These modifications consist of an extension to 3D, the ability of tiles to form "flexible" bonds that allow bound tiles to rotate relative to each other, and allowing tiles of multiple shapes within the same system. We call this new model the STAM*, and we present a series of constructions within it that are capable of self-replicating behavior. Namely, the input seed assemblies to our STAM* systems can encode either "genomes" specifying the instructions for building a target shape, or can be copies of the target shape with instructions built in. A universal tile set exists for any target shape (at scale factor 2), and from a genome assembly creates infinite copies of the genome as well as the target shape. An input target structure, on the other hand, can be "deconstructed" by the universal tile set to form a genome encoding it, which will then replicate and also initiate the growth of copies of assemblies of the target shape. Since the lengths of the genomes for these constructions are proportional to the number of points in the target shape, we also present a replicator which utilizes hierarchical self-assembly to greatly reduce the size of the genomes required. The main goals of this work are to examine minimal requirements of self-assembling systems capable of self-replicating behavior, with the aim of better understanding self-replication in nature as well as understanding the complexity of mimicking it.

Subject Classification

ACM Subject Classification
  • Theory of computation → Models of computation
  • General and reference → General conference proceedings
Keywords
  • Algorithmic self-assembly
  • tile assembly model
  • self-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 Demaine, Martin Demaine, Robin Flatland, Scott Kominers, and Robert Schweller. 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, 2010. Society for Industrial and Applied Mathematics. Google Scholar
  2. Andrew Alseth, Daniel Hader, and Matthew J. Patitz. Self-replication via tile self-assembly (extended abstract). Technical Report 2105.02914, Computing Research Repository, 2021. URL: http://arxiv.org/abs/2105.02914.
  3. Ebbe S. Andersen, Mingdong Dong, Morten M. Nielsen, Kasper Jahn, Ramesh Subramani, Wael Mamdouh, Monika M. Golas, Bjoern Sander, Holger Stark, Cristiano L. P. Oliveira, Jan S. Pedersen, Victoria Birkedal, Flemming Besenbacher, Kurt V. Gothelf, and Jorgen Kjems. Self-assembly of a nanoscale dna box with a controllable lid. Nature, 459(7243):73-76, May 2009. URL: https://doi.org/10.1038/nature07971.
  4. Robert D. Barish, Rebecca Schulman, Paul W. K. Rothemund, and Erik Winfree. An information-bearing seed for nucleating algorithmic self-assembly. Proceedings of the National Academy of Sciences, 106(15):6054-6059, April 2009. URL: https://doi.org/10.1073/pnas.0808736106.
  5. Florent Becker, Ivan Rapaport, and Eric Rémila. Self-assembling classes of shapes with a minimum number of tiles, and in optimal time. In Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 45-56, 2006. URL: https://doi.org/10.1007/11944836_7.
  6. Florent Becker, Eric Rémila, and Nicolas Schabanel. Time optimal self-assembly for 2d and 3d shapes: The case of squares and cubes. In Ashish Goel, Friedrich C. Simmel, and Petr Sosík, editors, DNA, volume 5347 of Lecture Notes in Computer Science, pages 144-155. Springer, 2008. URL: https://doi.org/10.1007/978-3-642-03076-5_12.
  7. Hieu Bui, Shalin Shah, Reem Mokhtar, Tianqi Song, Sudhanshu Garg, and John Reif. Localized dna hybridization chain reactions on dna origami. ACS nano, 12(2):1146-1155, 2018. Google Scholar
  8. 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
  9. Kenneth C Cheung, Erik D Demaine, Jonathan R Bachrach, and Saul Griffith. Programmable assembly with universally foldable strings (moteins). IEEE Transactions on Robotics, 27(4):718-729, 2011. Google Scholar
  10. Matthew Cook, Yunhui Fu, and Robert T. Schweller. Temperature 1 self-assembly: Deterministic assembly in 3D and probabilistic assembly in 2D. In SODA 2011: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2011. Google Scholar
  11. 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
  12. 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.
  13. 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
  14. Erik D. Demaine, Matthew J. Patitz, Trent A. Rogers, Robert T. Schweller, Scott M. Summers, and Damien Woods. The two-handed tile assembly model is not intrinsically universal. Algorithmica, 74(2):812-850, February 2016. URL: https://doi.org/10.1007/s00453-015-9976-y.
  15. David Doty. Randomized self-assembly for exact shapes. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 85-94. IEEE, 2009. Google Scholar
  16. David Doty, Lila Kari, and Benoît Masson. Negative interactions in irreversible self-assembly. Algorithmica, 66(1):153-172, 2013. URL: https://doi.org/10.1007/s00453-012-9631-9.
  17. 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
  18. 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 Proceedings of the 24th International Conference on DNA Computing and Molecular Programming (DNA 24), Shandong Normal University, Jinan, China October 8-12, pages 105-121, 2018. Google Scholar
  19. Sándor P. Fekete, Jacob Hendricks, Matthew J. Patitz, Trent A. Rogers, and Robert T. Schweller. Universal computation with arbitrary polyomino tiles in non-cooperative self-assembly. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), San Diego, CA, USA January 4-6, 2015, pages 148-167, 2015. URL: https://doi.org/10.1137/1.9781611973730.12.
  20. 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
  21. Bin Fu, Matthew J. Patitz, Robert T. Schweller, and Robert Sheline. Self-assembly with geometric tiles. In Proceedings of the 39th International Colloquium on Automata, Languages and Programming, ICALP, pages 714-725, 2012. Google Scholar
  22. David Furcy, Samuel Micka, and Scott M. Summers. Optimal program-size complexity for self-assembly at temperature 1 in 3D. In DNA Computing and Molecular Programming - 21st International Conference, DNA 21, Boston and Cambridge, MA, USA, August 17-21, 2015. Proceedings, pages 71-86, 2015. URL: https://doi.org/10.1007/978-3-319-21999-8_5.
  23. Oscar Gilbert, Jacob Hendricks, Matthew J. Patitz, and Trent A. Rogers. Computing in continuous space with self-assembling polygonal tiles. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), Arlington, VA, USA January 10-12, 2016, pages 937-956, 2016. Google Scholar
  24. Daniel Hader, Aaron Koch, Matthew J. Patitz, and Michael Sharp. The impacts of dimensionality, diffusion, and directedness on intrinsic universality in the abstract tile assembly model. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 2607-2624. SIAM, 2020. Google Scholar
  25. Daniel Hader and Matthew J. Patitz. Geometric tiles and powers and limitations of geometric hindrance in self-assembly. In Proceedings of the 18th Annual Conference on Unconventional Computation and Natural Computation (UCNC 2019), Tokyo, Japan June 3–7, 2019, pages 191-204, 2019. Google Scholar
  26. 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
  27. 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.
  28. 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.
  29. Jacob Hendricks, Matthew J. Patitz, and Trent A. Rogers. The simulation powers and limitations of higher temperature hierarchical self-assembly systems. Fundam. Inform., 155(1-2):131-162, 2017. URL: https://doi.org/10.3233/FI-2017-1579.
  30. 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.
  31. 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.
  32. Nataša Jonoska and Gregory L. McColm. A computational model for self-assembling flexible tiles. In Proceedings of the 4th international conference on Unconventional Computation, UC'05, pages 142-156, Berlin, Heidelberg, 2005. Springer-Verlag. URL: https://doi.org/10.1007/11560319_14.
  33. Nataša Jonoska and Gregory L. McColm. Complexity classes for self-assembling flexible tiles. Theor. Comput. Sci., 410(4-5):332-346, 2009. URL: https://doi.org/10.1016/j.tcs.2008.09.054.
  34. Nataša Jonoska and GregoryL. McColm. Flexible versus rigid tile assembly. In CristianS. Calude, MichaelJ. Dinneen, Gheorghe Păun, Grzegorz Rozenberg, and Susan Stepney, editors, Unconventional Computation, volume 4135 of Lecture Notes in Computer Science, pages 139-151. Springer Berlin Heidelberg, 2006. URL: https://doi.org/10.1007/11839132_12.
  35. Lila Kari, Shinnosuke Seki, and Zhi Xu. Triangular and hexagonal tile self-assembly systems. In Proceedings of the 2012 international conference on Theoretical Computer Science: computation, physics and beyond, WTCS'12, pages 357-375, Berlin, Heidelberg, 2012. Springer-Verlag. URL: https://doi.org/10.1007/978-3-642-27654-5_28.
  36. Alexandra Keenan, Robert Schweller, and Xingsi Zhong. Exponential replication of patterns in the signal tile assembly model. Natural Computing, 14(2):265-278, 2014. Google Scholar
  37. 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.
  38. 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.
  39. Wenyan Liu, Hong Zhong, Risheng Wang, and Nadrian C. Seeman. Crystalline two-dimensional dna-origami arrays. Angewandte Chemie International Edition, 50(1):264-267, 2011. URL: https://doi.org/10.1002/anie.201005911.
  40. 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
  41. Jennifer E. Padilla, Ruojie Sha, Martin Kristiansen, Junghuei Chen, Natasha Jonoska, and Nadrian C. Seeman. A signal-passing DNA-strand-exchange mechanism for active self-assembly of DNA nanostructures. Angewandte Chemie International Edition, 54(20):5939-5942, March 2015. URL: https://doi.org/10.1002/anie.201500252.
  42. Matthew J. Patitz, Trent A. Rogers, Robert T. Schweller, Scott M. Summers, and Andrew Winslow. Resiliency to multiple nucleation in temperature-1 self-assembly. In Proceedings of the 22nd International Conference on DNA Computing and Molecular Programming (DNA 22), Ludwig-Maximilians-Universität, Munich, Germany September 4-8, 2016, pages 98-113, 2016. Google Scholar
  43. Lulu Qian and Erik Winfree. Scaling up digital circuit computation with dna strand displacement cascades. Science, 332(6034):1196-1201, 2011. Google Scholar
  44. P. W. K. Rothemund. Design of dna origami. In ICCAD '05: Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, pages 471-478, Washington, DC, USA, 2005. IEEE Computer Society. Google Scholar
  45. 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. URL: https://doi.org/10.1145/335305.335358.
  46. Rebecca Schulman, Bernard Yurke, and Erik Winfree. Robust self-replication of combinatorial information via crystal growth and scission. Proc Natl Acad Sci USA, 109(17):6405-10, 2012. URL: http://www.biomedsearch.com/nih/Robust-self-replication-combinatorial-information/22493232.html.
  47. Friedrich C. Simmel, Bernard Yurke, and Hari R. Singh. Principles and applications of nucleic acid strand displacement reactions. Chemical Reviews, 119(10):6326-6369, 2019. Google Scholar
  48. David Soloveichik and Erik Winfree. Complexity of compact proofreading for self-assembled patterns. In The eleventh International Meeting on DNA Computing, 2005. Google Scholar
  49. 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.
  50. 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.
  51. Boya Wang, Chris Thachuk, Andrew D. Ellington, Erik Winfree, and David Soloveichik. Effective design principles for leakless strand displacement systems. Proceedings of the National Academy of Sciences, 115(52):E12182-E12191, 2018. Google Scholar
  52. Bryan Wei, Mingjie Dai, and Peng Yin. Complex shapes self-assembled from single-stranded dna tiles. Nature, 485(7400):623-626, 2012. Google Scholar
  53. David Yu Zhang and Rizal F. Hariadi. Integrating dna strand-displacement circuitry with dna tile self-assembly. Nature Communications, 4(6):Art. No. 1965, June 2013. Google Scholar
  54. David Yu Zhang and Georg Seelig. Dynamic dna nanotechnology using strand-displacement reactions. Nature chemistry, 3(2):103-113, 2011. 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 About DROPS Imprint Privacy Contact