Document Open Access Logo

The Topology of Scaffold Routings on Non-Spherical Mesh Wireframes

Authors Abdulmelik Mohammed, Nataša Jonoska, Masahico Saito

PDF
Thumbnail PDF

File

LIPIcs.DNA.2020.1.pdf
  • Filesize: 0.52 MB
  • 17 pages

Document Identifiers

Author Details

Abdulmelik Mohammed
  • Department of Mathematics and Statistics, University of South Florida, Tampa, FL, USA
Nataša Jonoska
  • Department of Mathematics and Statistics, University of South Florida, Tampa, FL, USA
Masahico Saito
  • Department of Mathematics and Statistics, University of South Florida, Tampa, FL, USA

Funding

This research was (partially) supported by the grants NSF DMS-1800443/1764366 and the Southeast Center for Mathematics and Biology, an NSF-Simons Research Center for Mathematics of Complex Biological Systems, under National Science Foundation Grant No. DMS-1764406 and Simons Foundation Grant No. 594594. Travel support is provided to Abdulmelik Mohammed through an AMS-Simons Travel Grant (2020).

Cite As Get BibTex

Abdulmelik Mohammed, Nataša Jonoska, and Masahico Saito. The Topology of Scaffold Routings on Non-Spherical Mesh Wireframes. In 26th International Conference on DNA Computing and Molecular Programming (DNA 26). Leibniz International Proceedings in Informatics (LIPIcs), Volume 174, pp. 1:1-1:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.DNA.2020.1

Abstract

The routing of a DNA-origami scaffold strand is often modelled as an Eulerian circuit of an Eulerian graph in combinatorial models of DNA origami design. The knot type of the scaffold strand dictates the feasibility of an Eulerian circuit to be used as the scaffold route in the design. Motivated by the topology of scaffold routings in 3D DNA origami, we investigate the knottedness of Eulerian circuits on surface-embedded graphs. We show that certain graph embeddings, checkerboard colorable, always admit unknotted Eulerian circuits. On the other hand, we prove that if a graph admits an embedding in a torus that is not checkerboard colorable, then it can be re-embedded so that all its non-intersecting Eulerian circuits are knotted. For surfaces of genus greater than one, we present an infinite family of checkerboard-colorable graph embeddings where there exist knotted Eulerian circuits.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Discrete mathematics
Keywords
  • DNA origami
  • Scaffold routing
  • Graphs
  • Surfaces
  • Knots
  • Eulerian circuits

Metrics

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

References

  1. Jaromir Abrham and Anton Kotzig. Construction of planar Eulerian multigraphs. In Proc. Tenth Southeastern Conf. Comb., Graph Theory, and Computing, pages 123-130, 1979. Google Scholar
  2. Leonard M. Adleman. Molecular computation of solutions to combinatorial problems. Science, 266(5187):1021-1024, 1994. URL: https://doi.org/10.1126/SCIENCE.7973651.
  3. Mark A. Armstrong. Basic Topology. Springer New York, 1983. Google Scholar
  4. Erik Benson, Abdulmelik Mohammed, Alessandro Bosco, Ana I. Teixeira, Pekka Orponen, and Björn Högberg. Computer-aided production of scaffolded DNA nanostructures from flat sheet meshes. Angewandte Chemie International Edition, 55(31):8869-8872, 2016. URL: https://doi.org/10.1002/anie.201602446.
  5. Erik Benson, Abdulmelik Mohammed, Johan Gardell, Sergej Masich, Eugen Czeizler, Pekka Orponen, and Björn Högberg. DNA rendering of polyhedral meshes at the nanoscale. Nature, 523(7561):441-444, 2015. URL: https://doi.org/10.1038/nature14586.
  6. Samuel W. Bent and Udi Manber. On non-intersecting Eulerian circuits. Discrete Applied Mathematics, 18(1):87-94, 1987. URL: https://doi.org/10.1016/0166-218X(87)90045-X.
  7. Dorothy Buck, Egor Dolzhenko, Nataša Jonoska, Masahico Saito, and Karin Valencia. Genus ranges of 4-regular rigid vertex graphs. Electronic Journal of Combinatorics, 22(3):P3.43, 2015. Google Scholar
  8. Junghuei Chen and Nadrian C. Seeman. Synthesis from DNA of a molecule with the connectivity of a cube. Nature, 350(6319):631-633, 1991. URL: https://doi.org/10.1038/350631a0.
  9. Joanna A. Ellis-Monaghan, Greta Pangborn, Nadrian C. Seeman, Sam Blakeley, Conor Disher, Mary Falcigno, Brianna Healy, Ada Morse, Bharti Singh, and Melissa Westland. Design tools for reporter strands and DNA origami scaffold strands. Theoretical Computer Science, 671:69-78, 2017. URL: https://doi.org/10.1016/j.tcs.2016.10.007.
  10. Herbert Fleischner. Eulerian Graphs and Related Topics. Part 1, Volume 1, volume 45 of Annals of Discrete Mathematics. North-Holland Publishing Co., Amsterdam, 1990. Google Scholar
  11. R. P. Goodman, I. A. T. Schaap, C. F. Tardin, C. M. Erben, R. M. Berry, C. F. Schmidt, and A. J. Turberfield. Rapid chiral assembly of rigid DNA building blocks for molecular nanofabrication. Science, 310(5754):1661-1665, 2005. URL: https://doi.org/10.1126/science.1120367.
  12. Jonathan L. Gross and Thomas W. Tucker. Topological Graph Theory. Dover Publications, INC, 2001. Dover reprint, original published in 1987. Google Scholar
  13. Yu He, Tao Ye, Min Su, Chuan Zhang, Alexander E. Ribbe, Wen Jiang, and Chengde Mao. Hierarchical self-assembly of DNA into symmetric supramolecular polyhedra. Nature, 452(7184):198-201, 2008. URL: https://doi.org/10.1038/nature06597.
  14. Ryosuke Iinuma, Yonggang Ke, Ralf Jungmann, Thomas Schlichthaerle, Johannes B. Woehrstein, and Peng Yin. Polyhedra self-assembled from DNA tripods and characterized with 3D DNA-PAINT. Science, 344(6179):65-69, 2014. URL: https://doi.org/10.1126/science.1250944.
  15. Nataša Jonoska, Stephen A. Karl, and Masahico Saito. Creating 3-dimensional graph structures with DNA. In Harvey Rubin and David H. Wood, editors, DNA Based Computers III, volume 48 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 123-136. AMS and DIMACS, 1999. Google Scholar
  16. Nataša Jonoska and Masahico Saito. Boundary components of thickened graphs. In Nataša Jonoska and Nadrian C. Seeman, editors, 7th International Workshop on DNA-Based Computers, volume 2340 of Lecture Notes in Computer Science, pages 70-81. Springer, 2001. URL: https://doi.org/10.1007/3-540-48017-X_7.
  17. Hyungmin Jun, Tyson R. Shepherd, Kaiming Zhang, William P. Bricker, Shanshan Li, Wah Chiu, and Mark Bathe. Automated sequence design of 3D polyhedral wireframe DNA origami with honeycomb edges. ACS Nano, 13(2):2083-2093, 2019. URL: https://doi.org/10.1021/acsnano.8b08671.
  18. Hyungmin Jun, Xiao Wang, William P. Bricker, and Mark Bathe. Automated sequence design of 2D wireframe DNA origami with honeycomb edges. Nature Communications, 10(5419):1-9, 2019. URL: https://doi.org/10.1038/s41467-019-13457-y.
  19. Hyungmin Jun, Fei Zhang, Tyson Shepherd, Sakul Ratanalert, Xiaodong Qi, Hao Yan, and Mark Bathe. Autonomously designed free-form 2D DNA origami. Science Advances, 5(1), 2019. URL: https://doi.org/10.1126/sciadv.aav0655.
  20. Vid Kočar, John S. Schreck, Slavko Čeru, Helena Gradišar, Nino Bašić, Tomaž Pisanski, Jonathan P. K. Doye, and Roman Jerala. Design principles for rapid folding of knotted DNA nanostructures. Nature Communications, 7:10803, 2016. URL: https://doi.org/10.1038/ncomms10803.
  21. Ajasja Ljubetič, Fabio Lapenta, Helena Gradišar, Igor Drobnak, Jana Aupič, Žiga Strmšek, Duško Lainšček, Iva Hafner-Bratkovič, Andreja Majerle, Nuša Krivec, Mojca Benčina, Tomaž Pisanski, Tanja Ćirković Veličković, Adam Round, José María Carazo, Roberto Melero, and Roman Jerala. Design of coiled-coil protein-origami cages that self-assemble in vitro and in vivo. Nature Biotechnology, 35(11):1094-1101, 2017. URL: https://doi.org/10.1038/nbt.3994.
  22. Abdulmelik Mohammed. Algorithmic Design of Biomolecular Nanostructures. PhD thesis, Aalto University, 2018. Google Scholar
  23. Abdulmelik Mohammed and Mustafa Hajij. Unknotted strand routings of triangulated meshes. In Robert Brijder and Lulu Qian, editors, DNA Computing and Molecular Programming, volume 10467 of Lecture Notes in Computer Science, pages 46-63. Springer, 2017. Google Scholar
  24. Ada Morse, William Adkisson, Jessica Greene, David Perry, Brenna Smith, Jo Ellis-Monaghan, and Greta Pangborn. DNA origami and unknotted A-trails in torus graphs. arXiv preprint arXiv:1703.03799, 2017. URL: http://arxiv.org/abs//arxiv.org/pdf/1703.03799.pdf.
  25. Dale Rolfsen. Knots and Links. AMS Chelsea Publishing, 2003. Reprint, original print in 1976. Google Scholar
  26. Paul W. K. Rothemund. Folding DNA to create nanoscale shapes and patterns. Nature, 440(7082):297-302, 2006. URL: https://doi.org/10.1038/nature04586.
  27. Phiset Sa-Ardyen, Nataša Jonoska, and Nadrian C. Seeman. Self-assembling DNA graphs. Natural Computing, 2:427-438, 2003. URL: https://doi.org/10.1023/B:NACO.0000006771.95566.34.
  28. Nadrian C. Seeman. Nucleic-acid junctions and lattices. Journal of Theoretical Biology, 99(2):237-247, 1982. URL: https://doi.org/10.1016/0022-5193(82)90002-9.
  29. Nadrian C. Seeman and Neville R. Kallenbach. Design of immobile nucleic acid junctions. Biophysical Journal, 44(2):201-209, 1983. URL: https://doi.org/10.1016/S0006-3495(83)84292-1.
  30. William M. Shih, Joel D. Quispe, and Gerald F. Joyce. A 1.7-kilobase single-stranded DNA that folds into a nanoscale octahedron. Nature, 427(6975):618-621, 2004. URL: https://doi.org/10.1038/nature02307.
  31. Mu-Tsun Tsai and Douglas B. West. A new proof of 3-colorability of Eulerian triangulations. Ars Mathematica Contemporanea, 4(1):73-77, 2011. Google Scholar
  32. Rémi Veneziano, Sakul Ratanalert, Kaiming Zhang, Fei Zhang, Hao Yan, Wah Chiu, and Mark Bathe. Designer nanoscale DNA assemblies programmed from the top down. Science, 352(6293):1534, 2016. URL: https://doi.org/10.1126/science.aaf4388.
  33. Gang Wu, Nataša Jonoska, and Nadrian C. Seeman. Construction of a DNA nano-object directly demonstrates computation. Biosystems, 98(2):80-84, 2009. URL: https://doi.org/10.1016/j.biosystems.2009.07.004.
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