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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
By convention, if \(k=0\), then \(v_0\) is affinely independent.
- 2.
Detachments are also defined in the literature [11] for multigraphs without an associated embedding.
- 3.
\(X^{\star }\) is the subgraph of the dual of M induced by the duals of the cut edges.
- 4.
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.
References
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)
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)
Chen, J., Seeman, N.C.: Synthesis from DNA of a molecule with the connectivity of a cube. Nature 350(6319), 631 (1991)
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)
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)
Edmonds, J., Johnson, E.L.: Matching, Euler tours and the Chinese postman. Math. Program. 5(1), 88–124 (1973)
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)
Erickson, J., Har-Peled, S.: Optimally cutting a surface into a disk. Discrete Comput. Geom. 31(1), 37–59 (2004)
Euler, L.: Solutio problematis ad geometriam situs pertinentis. Commentarii Academiae Scientiarum Petropolitanae 8, 128–140 (1741)
Fleischner, H.: Eulerian Graphs and Related Topics, vol. 1. Elsevier, Amsterdam (1990)
Floater, M.S.: Parametrization and smooth approximation of surface triangulations. Comput. Aided Geom. Des. 14(3), 231–250 (1997)
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)
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)
Gross, J., Yellen, J.: Handbook of Graph Theory. Discrete Mathematics and Its Applications. CRC Press, Boca Raton (2004)
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)
Hierholzer, C., Wiener, C.: Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren. Mathematische Annalen 6(1), 30–32 (1873)
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)
Jungnickel, D., Schade, T.: Graphs, Networks and Algorithms. Springer, New York (2008)
Ke, Y., Ong, L.L., Shih, W.M., Yin, P.: Three-dimensional structures self-assembled from DNA bricks. Science 338(6111), 1177–1183 (2012)
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)
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)
Lee, J.: Introduction to Topological Manifolds, vol. 940. Springer Science & Business Media, New York (2010)
Lickorish, W.R.: An Introduction to Knot Theory, vol. 175. Springer Science & Business Media, New York (2012)
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)
Rolfsen, D.: Knots and Links, vol. 346. American Mathematical Society, Providence (1976)
Rothemund, P.W.: Folding DNA to create nanoscale shapes and patterns. Nature 440(7082), 297–302 (2006)
Rothemund, P.W., Papadakis, N., Winfree, E.: Algorithmic self-assembly of DNA Sierpinski triangles. PLoS Biol. 2(12), e424 (2004)
Seeman, N.C.: Nucleic acid junctions and lattices. J. Theoret. Biol. 99(2), 237–247 (1982)
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)
Singmaster, D., Grossman, J.W.: E2897. Am. Math. Mon. 90(4), 287–288 (1983)
Tsai, M.T., West, D.B.: A new proof of 3-colorability of Eulerian triangulations. Ars Mathematica Contemporanea 4(1), 73–77 (2011)
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)
Wei, B., Dai, M., Yin, P.: Complex shapes self-assembled from single-stranded DNA tiles. Nature 485(7400), 623–626 (2012)
Wu, G., Jonoska, N., Seeman, N.C.: Construction of a DNA nano-object directly demonstrates computation. Biosystems 98(2), 80–84 (2009)
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)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Mohammed, A., Hajij, M. (2017). Unknotted Strand Routings of Triangulated Meshes. In: Brijder, R., Qian, L. (eds) DNA Computing and Molecular Programming. DNA 2017. Lecture Notes in Computer Science(), vol 10467. Springer, Cham. https://doi.org/10.1007/978-3-319-66799-7_4
Download citation
DOI: https://doi.org/10.1007/978-3-319-66799-7_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-66798-0
Online ISBN: 978-3-319-66799-7
eBook Packages: Computer ScienceComputer Science (R0)