Document Open Access Logo

Small Tile Sets That Compute While Solving Mazes

Authors Matthew Cook, Tristan Stérin , Damien Woods

PDF
Thumbnail PDF

File

LIPIcs.DNA.27.8.pdf
  • Filesize: 1.72 MB
  • 20 pages

Document Identifiers

Author Details

Matthew Cook
  • Institute of Neuroinformatics, University of Zürich and ETH Zürich, Switzerland
Tristan Stérin
  • Hamilton Institute, Department of Computer Science, Maynooth University, Ireland
Damien Woods
  • Hamilton Institute, Department of Computer Science, Maynooth University, Ireland

Funding

Research of Woods and Stérin 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, both to D Woods.

Acknowledgements

We thank Trent Rogers, Niall Murphy, Pierre Marcus and Nicolas Schabanel for useful discussions on the Maze-Walking Tile Assembly Model.

Cite As Get BibTex

Matthew Cook, Tristan Stérin, and Damien Woods. Small Tile Sets That Compute While Solving Mazes. In 27th International Conference on DNA Computing and Molecular Programming (DNA 27). Leibniz International Proceedings in Informatics (LIPIcs), Volume 205, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.DNA.27.8

Abstract

We ask the question of how small a self-assembling set of tiles can be yet have interesting computational behaviour. We study this question in a model where supporting walls are provided as an input structure for tiles to grow along: we call it the Maze-Walking Tile Assembly Model. The model has a number of implementation prospects, one being DNA strands that attach to a DNA origami substrate. Intuitively, the model suggests a separation of signal routing and computation: the input structure (maze) supplies a routing diagram, and the programmer’s tile set provides the computational ability. We ask how simple the computational part can be.
We give two tiny tile sets that are computationally universal in the Maze-Walking Tile Assembly Model. The first has four tiles and simulates Boolean circuits by directly implementing NAND, NXOR and NOT gates. Our second tile set has 6 tiles and is called the Collatz tile set as it produces patterns found in binary/ternary representations of iterations of the Collatz function. Using computer search we find that the Collatz tile set is expressive enough to encode Boolean circuits using blocks of these patterns. These two tile sets give two different methods to find simple universal tile sets, and provide motivation for using pre-assembled maze structures as circuit wiring diagrams in molecular self-assembly based computing.

Subject Classification

ACM Subject Classification
  • Theory of computation → Models of computation
  • Theory of computation → Computational geometry
Keywords
  • model of computation
  • self-assembly
  • small universal tile set
  • Boolean circuits
  • maze-solving

Metrics

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

Related Versions

Supplementary Materials

References

  1. Eric Allender, David A Mix Barrington, Tanmoy Chakraborty, Samir Datta, and Sambuddha Roy. Planar and grid graph reachability problems. Theory of Computing Systems, 45(4):675-723, 2009. Google Scholar
  2. Tatiana Brailovskaya, Gokul Gowri, Sean Yu, and Erik Winfree. Reversible computation using swap reactions on a surface. In Chris Thachuk and Yan Liu, editors, DNA Computing and Molecular Programming, pages 174-196, Cham, 2019. Springer International Publishing. Google Scholar
  3. Hieu Bui, Vincent Miao, Sudhanshu Garg, Reem Mokhtar, Tianqi Song, and John Reif. Design and analysis of localized DNA hybridization chain reactions. Small, 13(12):1602983, 2017. Google Scholar
  4. 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, February 2018. Google Scholar
  5. Angel A Cantu, Austin Luchsinger, Robert Schweller, and Tim Wylie. Covert computation in self-assembled circuits. Algorithmica, 83(2):531-552, 2021. arXiv preprint: URL: https://arxiv.org/abs/1908.06068.
  6. A. R. Chandrasekaran, O. Levchenko, D. S. Patel, M. MacIsaac, and K. Halvorsen. Addressable configurations of DNA nanostructures for rewritable memory. Nucleic Acids Res, 45(19):11459-11465, November 2017. Google Scholar
  7. Jie Chao, Jianbang Wang, Fei Wang, Xiangyuan Ouyang, Enzo Kopperger, Huajie Liu, Qian Li, Jiye Shi, Lihua Wang, Jun Hu, Lianhui Wang, Wei Huang, Friedrich C. Simmel, and Chunhai Fan. Solving mazes with single-molecule DNA navigators. Nature Materials, 18(3):273-279, March 2019. Google Scholar
  8. Gourab Chatterjee, Neil Dalchau, Richard A. Muscat, Andrew Phillips, and Georg Seelig. A spatially localized architecture for fast and modular DNA computing. Nature Nanotechnology, 12(9):920-927, September 2017. Google Scholar
  9. Marek Chrobak and Thomas H Payne. A linear-time algorithm for drawing a planar graph on a grid. Information Processing Letters, 54(4):241-246, 1995. Google Scholar
  10. Samuel Clamons, Lulu Qian, and Erik Winfree. Programming and simulating chemical reaction networks on a surface. Journal of The Royal Society Interface, 17(166):20190790, 2020. Google Scholar
  11. Matthew Cook. Universality in elementary cellular automata. Complex Systems, 15, 2004. Google Scholar
  12. Neil Dalchau, Harish Chandran, Nikhil Gopalkrishnan, Andrew Phillips, and John Reif. Probabilistic analysis of localized DNA hybridization circuits. ACS synthetic biology, 4(8):898-913, 2015. Google Scholar
  13. Frits Dannenberg, Marta Kwiatkowska, Chris Thachuk, and Andrew J. Turberfield. DNA walker circuits: Computational potential, design, and verification. In David Soloveichik and Bernard Yurke, editors, DNA Computing and Molecular Programming, pages 31-45, Cham, 2013. Springer International Publishing. Google Scholar
  14. Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Matthew J. Patitz, Robert T. Schweller, Andrew Winslow, and Damien Woods. One tile to rule them all: Simulating any tile assembly system with a single universal tile. In ICALP: Proceedings of the 41st International Colloquium on Automata, Languages, and Programming, volume 8572 of LNCS, pages 368-379. Springer, 2014. Arxiv preprint: URL: http://arxiv.org/abs/1212.4756.
  15. 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. In ICALP: Proceedings of the 40th International Colloquium on Automata, Languages, and Programming, volume 7965 of LNCS, pages 400-412. Springer, 2013. Arxiv preprint: URL: http://arxiv.org/abs/1306.6710.
  16. David Doty. Theory of algorithmic self-assembly. Communications of the ACM, 55(12):78-88, 2012. Google Scholar
  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 FOCS: Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, pages 439-446. IEEE, 2012. Arxiv preprint: URL: http://arxiv.org/abs/1111.3097.
  18. Paul Erdös. Some unconventional problems in number theory. Mathematics Magazine, 52(2):67-70, 1979. URL: https://doi.org/10.1080/0025570X.1979.11976756.
  19. Constantine Evans. Crystals that count! Physical principles and experimental investigations of DNA tile self-assembly. PhD thesis, Caltech, 2014. Google Scholar
  20. Hongzhou Gu, Jie Chao, Shou-Jun Xiao, and Nadrian C Seeman. A proximity-based programmable DNA nanoscale assembly line. Nature, 465(7295):202-205, 2010. Google Scholar
  21. William Hesse, Eric Allender, and David A Mix Barrington. Uniform constant-depth threshold circuits for division and iterated multiplication. Journal of Computer and System Sciences, 65(4):695-716, 2002. Google Scholar
  22. Neil Immerman. Descriptive Complexity. Springer, 1999. Google Scholar
  23. Jeffrey C. Lagarias. The 3x + 1 problem and its generalizations. The American Mathematical Monthly, 92(1):3-23, 1985. URL: http://www.jstor.org/stable/2322189.
  24. Jeffrey C. Lagarias. The 3x+1 problem: An annotated bibliography (1963-1999) (sorted by author), 2003. URL: http://arxiv.org/abs/math/0309224.
  25. Jeffrey C. Lagarias. Ternary expansions of powers of 2. Journal of the London Mathematical Society, 79(3):562-588, 2009. URL: https://doi.org/10.1112/jlms/jdn080.
  26. Matthew R Lakin, Rasmus Petersen, Kathryn E Gray, and Andrew Phillips. Abstract modelling of tethered DNA circuits. In International Workshop on DNA-Based Computers, pages 132-147. Springer, 2014. Google Scholar
  27. 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. Google Scholar
  28. Cristopher Moore and Stephan Mertens. The nature of computation. Oxford University Press, 2011. Google Scholar
  29. Niall Murphy and Damien Woods. AND and/or OR: Uniform polynomial-size circuits. In MCU 2013: Machines, Computations and Universality. Electronic Proceedings in Theoretical Computer Science (EPTCS), volume 128, pages 150-166, 2012. URL: https://arxiv.org/abs/1212.3282v2.
  30. Turlough Neary and Damien Woods. P-completeness of cellular automaton Rule 110. In ICALP: International Colloquium on Automata, Languages, and Programming, volume 4051, part 1 of LNCS, pages 132-143. Springer, 2006. Google Scholar
  31. Turlough Neary and Damien Woods. Four small universal Turing machines. Fundamenta Informaticae, 91(1):123-144, 2009. Google Scholar
  32. Turlough Neary and Damien Woods. Small weakly universal Turing machines. In International Symposium on Fundamentals of Computation Theory, pages 262-273. Springer, 2009. Google Scholar
  33. Tosan Omabegho, Ruojie Sha, and Nadrian C Seeman. A bipedal DNA brownian motor with coordinated legs. Science, 324(5923):67-71, 2009. Google Scholar
  34. Günther Pardatscher, Dan Bracha, Shirley S Daube, Ohad Vonshak, Friedrich C Simmel, and Roy H Bar-Ziv. DNA condensation in one dimension. Nature nanotechnology, 11(12):1076-1081, 2016. Google Scholar
  35. Matthew J. Patitz. An introduction to tile-based self-assembly and a survey of recent results. Natural Computing, 13(2):195-224, 2014. Google Scholar
  36. Lulu Qian and Erik Winfree. Parallel and scalable computation and spatial dynamics with DNA-based chemical reaction networks on a surface. In Satoshi Murata and Satoshi Kobayashi, editors, DNA Computing and Molecular Programming, pages 114-131, Cham, 2014. Springer International Publishing. Google Scholar
  37. John H. Reif and Sudheer Sahu. Autonomous programmable DNA nanorobotic devices using dnazymes. Theoretical Computer Science, 410(15):1428-1439, 2009. Aspects of Molecular Self-Assembly. Google Scholar
  38. Yuri Rogozhin. Small universal turing machines. Theoretical Computer Science, 168(2):215–240, 1996. Google Scholar
  39. Paul W K Rothemund and Erik Winfree. The program-size complexity of self-assembled squares. In STOC: Proceedings of the thirty-second annual ACM symposium on Theory of computing, pages 459-468. ACM, 2000. Google Scholar
  40. Paul WK Rothemund. Folding DNA to create nanoscale shapes and patterns. Nature, 440(7082):297-302, 2006. Google Scholar
  41. Sudheer Sahu, Thomas H LaBean, and John H Reif. A DNA nanotransport device powered by polymerase phi29. Nano letters, 8(11):3870—3878, November 2008. Google Scholar
  42. William B Sherman and Nadrian C Seeman. A precisely controlled DNA biped walking device. Nano letters, 4(7):1203-1207, 2004. Google Scholar
  43. 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.
  44. Tianqi Song, Shalin Shah, Hieu Bui, Sudhanshu Garg, Abeer Eshra, Daniel Fu, Ming Yang, Reem Mokhtar, and John Reif. Programming DNA-based biomolecular reaction networks on cancer cell membranes. Journal of the American Chemical Society, 141(42):16539-16543, October 2019. Google Scholar
  45. Darko Stefanovic. Maze exploration with molecular-scale walkers. In Adrian-Horia Dediu, Carlos Martín-Vide, and Bianca Truthe, editors, Theory and Practice of Natural Computing, pages 216-226, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. Google Scholar
  46. Tristan Stérin and Damien Woods. The Collatz process embeds a base conversion algorithm. In Sylvain Schmitz and Igor Potapov, editors, RP2020: 14th International Conference on Reachability Problems, volume 12448 of LNCS, pages 131-147. Springer, 2020. https://arxiv.org/abs/2007.06979 [cs.DM].
  47. Anupama J. Thubagere, Wei Li, Robert F. Johnson, Zibo Chen, Shayan Doroudi, Yae Lim Lee, Gregory Izatt, Sarah Wittman, Niranjan Srinivas, Damien Woods, Erik Winfree, and Lulu Qian. A cargo-sorting DNA robot. Science, 357(6356), 2017. Google Scholar
  48. Grigory Tikhomirov, Philip Petersen, and Lulu Qian. Fractal assembly of micrometre-scale DNA origami arrays with arbitrary patterns. Nature, 552(7683):67-71, 2017. Google Scholar
  49. Grigory Tikhomirov, Philip Petersen, and Lulu Qian. Programmable disorder in random DNA tilings. Nature nanotechnology, 12(3):251, 2017. Google Scholar
  50. Bryan Wei, Mingjie Dai, and Peng Yin. Complex shapes self-assembled from single-stranded DNA tiles. Nature, 485(7400):623-626, 2012. Google Scholar
  51. Shelley F. J. Wickham, Jonathan Bath, Yousuke Katsuda, Masayuki Endo, Kumi Hidaka, Hiroshi Sugiyama, and Andrew J. Turberfield. A DNA-based molecular motor that can navigate a network of tracks. Nature Nanotechnology, 7(3):169-173, March 2012. URL: https://doi.org/10.1038/nnano.2011.253.
  52. Erik Winfree. Algorithmic Self-Assembly of DNA. PhD thesis, California Institute of Technology, 1998. Google Scholar
  53. Erik Winfree, Furong Liu, Lisa A Wenzler, and Nadrian C Seeman. Design and self-assembly of two-dimensional DNA crystals. Nature, 394(6693):539-544, 1998. Google Scholar
  54. Günther J. Wirsching. The dynamical system generated by the 3n + 1 function. Springer, Berlin New York, 1998. Google Scholar
  55. Sungwook Woo and Paul WK Rothemund. Programmable molecular recognition based on the geometry of DNA nanostructures. Nature chemistry, 3(8):620, 2011. Google Scholar
  56. Damien Woods. Intrinsic universality and the computational power of self-assembly. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 373(2046):20140214, 2015. Google Scholar
  57. 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(7748):366-372, 2019. Google Scholar
  58. Damien Woods and Turlough Neary. The complexity of small universal Turing machines: A survey. Theoretical Computer Science, 410(4-5):443-450, 2009. Google Scholar
  59. Hao Yan, Thomas H. LaBean, Liping Feng, and John H. Reif. Directed nucleation assembly of DNA tile complexes for barcode-patterned lattices. Proceedings of the National Academy of Sciences, 100(14):8103-8108, 2003. Google Scholar
  60. P. Yin, H. Yan, X. G. Daniell, A. J. Turberfield, and J. H. Reif. A unidirectional DNA walker that moves autonomously along a track. Angewandte Chemie, 43(37):4906-4911, September 2004. 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