Top

Published in:

2017 | OriginalPaper | Chapter

Unknotted Strand Routings of Triangulated Meshes

Authors : Abdulmelik Mohammed, Mustafa Hajij

Published in: DNA Computing and Molecular Programming

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In molecular self-assembly such as DNA origami, a circular strand’s topological routing determines the feasibility of a design to assemble to a target. In this regard, the Chinese-postman DNA scaffold routings of Benson et al. (2015) only ensure the unknottedness of the scaffold strand for triangulated topological spheres. In this paper, we present a cubic-time \(\frac{5}{3}-\)approximation algorithm to compute unknotted Chinese-postman scaffold routings on triangulated orientable surfaces of higher genus. Our algorithm guarantees every edge is routed at most twice, hence permitting low-packed designs suitable for physiological conditions.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Ruleset Optimization on Isomorphic Oritatami Systems

next chapter The Design Space of Strand Displacement Cascades with Toehold-Size Clamps

By convention, if \(k=0\), then \(v_0\) is affinely independent.

Detachments are also defined in the literature [11] for multigraphs without an associated embedding.

\(X^{\star }\) is the subgraph of the dual of M induced by the duals of the cut edges.

Although stated only for Eulerian multigraphs embedded on a plane, Tsai and West’s proof also holds for Eulerian multigraphs embedded on any surface since the resplicing occurs locally at vertices.

Abrham, J., Kotzig, A.: Construction of planar Eulerian multigraphs. In: Proceedings of Tenth Southeastern Conference on Combinatorics, Graph Theory, and Computing, pp. 123–130 (1979)

Benson, E., Mohammed, A., Bosco, A., Teixeira, A.I., Orponen, P., Högberg, B.: Computer-aided production of scaffolded DNA nanostructures from flat sheet meshes. Angew. Chem. Int. Ed. 55(31), 8869–8872 (2016)CrossRef

Benson, E., Mohammed, A., Gardell, J., Masich, S., Czeizler, E., Orponen, P., Högberg, B.: DNA rendering of polyhedral meshes at the nanoscale. Nature 523(7561), 441–444 (2015)CrossRef

Chen, J., Seeman, N.C.: Synthesis from DNA of a molecule with the connectivity of a cube. Nature 350(6319), 631 (1991)CrossRef

Dey, T.K., Schipper, H.: A new technique to compute polygonal schema for 2-manifolds with application to null-homotopy detection. Discrete Comput. Geom. 14(1), 93–110 (1995)MathSciNetCrossRefMATH

Douglas, S.M., Dietz, H., Liedl, T., Högberg, B., Graf, F., Shih, W.M.: Self-assembly of DNA into nanoscale three-dimensional shapes. Nature 459(7245), 414–418 (2009)CrossRef

Edmonds, J., Johnson, E.L.: Matching, Euler tours and the Chinese postman. Math. Program. 5(1), 88–124 (1973)MathSciNetCrossRefMATH

Ellis-Monaghan, J.A., Pangborn, G., Seeman, N.C., Blakeley, S., Disher, C., Falcigno, M., Healy, B., Morse, A., Singh, B., Westland, M.: Design tools for reporter strands and DNA origami scaffold strands. Theoret. Comput. Sci. 671, 69–78 (2016)MathSciNetCrossRefMATH

Erickson, J., Har-Peled, S.: Optimally cutting a surface into a disk. Discrete Comput. Geom. 31(1), 37–59 (2004)MathSciNetCrossRefMATH

10.

Euler, L.: Solutio problematis ad geometriam situs pertinentis. Commentarii Academiae Scientiarum Petropolitanae 8, 128–140 (1741)

11.

Fleischner, H.: Eulerian Graphs and Related Topics, vol. 1. Elsevier, Amsterdam (1990)

12.

Floater, M.S.: Parametrization and smooth approximation of surface triangulations. Comput. Aided Geom. Des. 14(3), 231–250 (1997)MathSciNetCrossRefMATH

13.

Goodman, R.P., Schaap, I.A., Tardin, C.F., Erben, C.M., Berry, R.M., Schmidt, C.F., Turberfield, A.J.: Rapid chiral assembly of rigid DNA building blocks for molecular nanofabrication. Science 310(5754), 1661–1665 (2005)CrossRef

14.

Gradišar, H., Božič, S., Doles, T., Vengust, D., Hafner-Bratkovič, I., Mertelj, A., Webb, B., Šali, A., Klavžar, S., Jerala, R.: Design of a single-chain polypeptide tetrahedron assembled from coiled-coil segments. Nature Chem. Biol. 9(6), 362–366 (2013)CrossRef

15.

Gross, J., Yellen, J.: Handbook of Graph Theory. Discrete Mathematics and Its Applications. CRC Press, Boca Raton (2004)MATH

16.

He, Y., Ye, T., Su, M., Zhang, C., Ribbe, A.E., Jiang, W., Mao, C.: Hierarchical self-assembly of DNA into symmetric supramolecular polyhedra. Nature 452(7184), 198–201 (2008)CrossRef

17.

Hierholzer, C., Wiener, C.: Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren. Mathematische Annalen 6(1), 30–32 (1873)MathSciNetCrossRefMATH

18.

Jonoska, N., Seeman, N.C., Wu, G.: On existence of reporter strands in DNA-based graph structures. Theoret. Comput. Sci. 410(15), 1448–1460 (2009)MathSciNetCrossRefMATH

19.

Jungnickel, D., Schade, T.: Graphs, Networks and Algorithms. Springer, New York (2008)

20.

Ke, Y., Ong, L.L., Shih, W.M., Yin, P.: Three-dimensional structures self-assembled from DNA bricks. Science 338(6111), 1177–1183 (2012)CrossRef

21.

Klavzar, S., Rus, J.: Stable traces as a model for self-assembly of polypeptide nanoscale polyhedrons. MATCH Commun. Math. Comput. Chem. 70, 317–330 (2013)MathSciNetMATH

22.

Kočar, V., Schreck, J.S., Čeru, S., Gradišar, H., Bašić, N., Pisanski, T., Doye, J.P., Jerala, R.: Design principles for rapid folding of knotted DNA nanostructures. Nature Commun. 7, 1–18 (2016)

23.

Lee, J.: Introduction to Topological Manifolds, vol. 940. Springer Science & Business Media, New York (2010)

24.

Lickorish, W.R.: An Introduction to Knot Theory, vol. 175. Springer Science & Business Media, New York (2012)

25.

Morse, A., Adkisson, W., Greene, J., Perry, D., Smith, B., Ellis-Monaghan, J., Pangborn, G.: DNA origami and unknotted A-trails in torus graphs. arXiv preprint arXiv:1703.03799 (2017)

26.

Rolfsen, D.: Knots and Links, vol. 346. American Mathematical Society, Providence (1976)

27.

Rothemund, P.W.: Folding DNA to create nanoscale shapes and patterns. Nature 440(7082), 297–302 (2006)CrossRef

28.

Rothemund, P.W., Papadakis, N., Winfree, E.: Algorithmic self-assembly of DNA Sierpinski triangles. PLoS Biol. 2(12), e424 (2004)CrossRef

29.

Seeman, N.C.: Nucleic acid junctions and lattices. J. Theoret. Biol. 99(2), 237–247 (1982)CrossRef

30.

Shih, W.M., Quispe, J.D., Joyce, G.F.: A 1.7-kilobase single-stranded DNA that folds into a nanoscale octahedron. Nature 427(6975), 618–621 (2004)CrossRef

31.

Singmaster, D., Grossman, J.W.: E2897. Am. Math. Mon. 90(4), 287–288 (1983)CrossRef

32.

Tsai, M.T., West, D.B.: A new proof of 3-colorability of Eulerian triangulations. Ars Mathematica Contemporanea 4(1), 73–77 (2011)MathSciNetMATH

33.

Veneziano, R., Ratanalert, S., Zhang, K., Zhang, F., Yan, H., Chiu, W., Bathe, M.: Designer nanoscale DNA assemblies programmed from the top down. Science 352(6293), 1534–1534 (2016)CrossRef

34.

Wei, B., Dai, M., Yin, P.: Complex shapes self-assembled from single-stranded DNA tiles. Nature 485(7400), 623–626 (2012)CrossRef

35.

Wu, G., Jonoska, N., Seeman, N.C.: Construction of a DNA nano-object directly demonstrates computation. Biosystems 98(2), 80–84 (2009)CrossRef

36.

Zheng, J., Birktoft, J.J., Chen, Y., Wang, T., Sha, R., Constantinou, P.E., Ginell, S.L., Mao, C., Seeman, N.C.: From molecular to macroscopic via the rational design of a self-assembled 3D DNA crystal. Nature 461(7260), 74–77 (2009)CrossRef

Title: Unknotted Strand Routings of Triangulated Meshes
Authors: Abdulmelik Mohammed
Mustafa Hajij
Publisher: Springer International Publishing
Book: DNA Computing and Molecular Programming
Print ISBN: 978-3-319-66798-0

Electronic ISBN: 978-3-319-66799-7

Copyright Year: 2017
DOI: https://doi.org/10.1007/978-3-319-66799-7_4

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner