Document Open Access Logo

On Algorithmic Self-Assembly of Squares by Co-Transcriptional Folding

Authors Szilárd Zsolt Fazekas , Hwee Kim, Ryuichi Matsuoka, Shinnosuke Seki , Hinano Takeuchi

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2022.37.pdf
  • Filesize: 10.49 MB
  • 15 pages

Document Identifiers

Author Details

Szilárd Zsolt Fazekas
  • Akita University, Japan
Hwee Kim
  • Incheon National University, Republic of Korea
Ryuichi Matsuoka
  • The University of Electro-Communications, Tokyo, Japan
Shinnosuke Seki
  • The University of Electro-Communications, Tokyo, Japan
Hinano Takeuchi
  • The University of Electro-Communications, Tokyo, Japan

Funding

  • Fazekas, Szilárd Zsolt: His research is supported by JSPS-KAKENHI Grant-in-Aid for Scientific Research (C) No. 19K11815.
  • Seki, Shinnosuke: His research is supported in part by JSPS-KAKENHI Grant-in-Aid for Scientific Research (B) No. 20H04141 and (C) No. 20K11672.

Acknowledgements

We would like to show our sincere gratitude towards Nicolas Schabanel and Ryuhei Uehara for their valuable comments in the development stage of the proposed square self-assembler. We would also like to thank the anonymous reviewers of ISAAC 2022 for their constructive comments, in particular for pointing out that mimicking the aTAM square construction’s encoding of n in a base larger than 2 would not be feasible with a periodic transcript. We also want to thank Naoya Iwano and Yu Kihara for proofreading earlier drafts.

Cite As Get BibTex

Szilárd Zsolt Fazekas, Hwee Kim, Ryuichi Matsuoka, Shinnosuke Seki, and Hinano Takeuchi. On Algorithmic Self-Assembly of Squares by Co-Transcriptional Folding. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ISAAC.2022.37

Abstract

Algorithms play a primary role in programming an orchestrated self-assembly of shapes into molecules. In this paper, we study the algorithmic self-assembly of squares by RNA co-transcriptional folding in its oritatami model. We formalize the square self-assembly problem in oritatami and propose a universal oritatami transcript made of 939 types of abstract molecules (beads) and of period 1294 that folds deterministically and co-transcriptionally at delay 3 and maximum arity into the n × n square modulo horizontal and vertical scaling factors for all sufficiently large n’s after building a Θ(log n) width "ruler" that measures n upon the seed of size Θ(log n) on which n is encoded in binary.

Subject Classification

ACM Subject Classification
  • Theory of computation → Models of computation
Keywords
  • Algorithmic molecular self-assembly
  • Co-transcriptional folding
  • Oritatami system
  • Self-assembly of squares

Metrics

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

Supplementary Materials

References

  1. Leonard Adleman, Qi Cheng, Ashish Goel, and Ming-Deh Huang. Running time and program size for self-assembled squares. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing (STOC 2001), pages 740-748. ACM, 2001. Google Scholar
  2. Gagan Aggarwal, Qi Cheng, Michael H. Goldwasser, Ming-Yang Kao, Pablo Moisset de Espanes, and Robert T. Schweller. Complexities for generalized models of self-assembly. SIAM Journal on Computing, 34(6):1493-1515, 2005. Google Scholar
  3. Florent Becker, Eric Rémila, and Nicolas Schabanel. Time optimal self-assembly for 2D and 3D shapes: The case of squares and cubes. In Proceedings of the 14th International Meeting on DNA Computing (DNA 14), volume 5347 of LNCS, pages 144-155. Springer, 2008. Google Scholar
  4. Erik D. Demaine, Jacob Hendricks, Meagan Olsen, Matthew J. Patitz, Trent A. Rogers, Nicolas Schabanel, Shinnosuke Seki, and Hadley Thomas. Know when to fold 'em: Self-assembly of shapes by folding in oritatami. In Proceedings of the 24th International Conference on DNA Computing and Molecular Programming (DNA 24), volume 11145 of LNCS, pages 19-36. Springer, 2018. Google Scholar
  5. Cody Geary, Guido Grossi, Ewan K. S. McRae, Paul W. K. Rothemund, and Ebbe S. Andersen. RNA origami design tools enable cotranscriptional folding of kilobase-sized nanoscaffolds. Nature Chemistry, 13:549-558, 2021. Google Scholar
  6. Cody Geary, Pierre-Étienne Meunier, Nicolas Schabanel, and Shinnosuke Seki. Programming biomolecules that fold greedily during transcription. In Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), volume 58 of LIPIcs, pages 43:1-43:14, 2016. Google Scholar
  7. Cody Geary, Pierre-Étienne Meunier, Nicolas Schabanel, and Shinnosuke Seki. Proving the turing universality of oritatami co-transcriptional folding. In Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC 2018), volume 123 of LIPIcs, pages 23:1-23:13, 2018. Google Scholar
  8. Cody Geary, Paul W. K. Rothemund, and Ebbe S. Andersen. A single-stranded architecture for cotranscriptional folding of RNA structures. Science, 345(6198):799-804, 2014. Google Scholar
  9. Yo-Sub Han and Hwee Kim. Construction of geometric structure by oritatami system. In Proceedings of the 24th International Conference on DNA Computing and Molecular Programming (DNA 24), volume 11145 of LNCS, pages 173-188, 2018. Google Scholar
  10. Yo-Sub Han and Hwee Kim. Impossibility of strict assembly of infinite fractals by oritatami. Natural Computing, 20(4):691-701, 2021. Google Scholar
  11. Kohei Maruyama and Shinnosuke Seki. Counting infinitely by oritatami co-transcriptional folding. Natural Computing, 20(2):329-340, 2021. Google Scholar
  12. Yusei Masuda, Shinnosuke Seki, and Yuki Ubukata. Towards the algorithmic molecular self-assembly of fractals by cotranscriptional folding. In Proceedings of the 23rd International Conference on Implementation and Application of Automata (CIAA 2018), volume 10977 of LNCS, pages 261-273, 2018. Google Scholar
  13. Evan C. Merkhofer, Peter Hu, and Tracy L. Johnson. Introduction to cotranscriptional RNA folding. In Methods in Moleclar Biology, volume 1126, pages 83-96. Springer, 2014. Google Scholar
  14. Samuel Nalin and Guillaume Theyssier. On turedo hierarchies and intrinsic universality. In Proceedings of the 28th International Conference on DNA Computing and Molecular Programming (DNA 28), volume 238 of LIPIcs, pages 6:1-6:18, 2022. Google Scholar
  15. 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
  16. Daria Pchelina, Nicolas Schabanel, Shinnosuke Seki, and Guillaume Theyssier. Oritatami systems assemble shapes no less complex than tile assembly model (aTAM). In Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), volume 219 of LIPIcs, pages 51:1-51:23, 2022. Google Scholar
  17. Daria Pchelina, Nicolas Schabanel, Shinnosuke Seki, and Yuki Ubukata. Simple intrinsic simulation of cellular automata in oritatami molecular folding model. In Proceedings of the 14th Latin American Symposium on Theoretical Informaitcs (LATIN 2020), volume 12118 of LNCS, pages 425-436, 2020. Google Scholar
  18. Roberto Perales and David Bentley. "Co-transcriptionality" - the transcription elongation complex as a nexus for nuclear transactions. Molecular Cell, 36(2):178-191, 2009. Google Scholar
  19. Paul W. K. Rothemund and Erik Winfree. The program-size complexity of self-assembled squares (extended abstracts). In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC 2000), pages 459-468. ACM, 2000. Google Scholar
  20. Alex van Belkum, Jan Pieter Abrahams, Gornelis W. A. Pleij, and Leender Bosch. Five pseudoknots are present at the 204 nucleotides long 3' noncoding region of tobacco mosaic virus RNA. Nucleic Acids Research, 13(1):7673-7686, 1985. Google Scholar
  21. Kyle E. Watters, Eric J. Strobel, Angela M. Yu, John T. Lis, and Julius B. Lucks. Cotranscriptional folding of a riboswitch at nucleotide resolution. Nature Structural and Molecular Biology, 23(12):1124-1131, 2016. Google Scholar
  22. Erik Winfree. Algorithmic Self-Assembly of DNA. PhD thesis, California Institute of Technology, 1998. 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