×

Design tools for reporter strands and DNA origami scaffold strands. (English) Zbl 1370.68091

Summary: Self-assembly using DNA origami methods requires determining a route for the scaffolding strand through the targeted structure. Here we provide strategies and software tools for determining optimal routes for reporter or scaffolding strands through graph-like (ball-and-rod) constructs. The approach applies to complex constructs, for example arbitrary geometric embeddings of graphs rather than surface meshes, lattice subsets, and meshes on higher genus surfaces than spheres. The software notably allows the user the flexibility of specifying ranked preferences for augmenting edges and for the possible configurations of branched junctions. The greater topological complexity of arbitrary graph embeddings and meshes on higher genus surfaces can result in scaffolding strand routes that are knotted in 3 space, so we also present necessary caveats for these settings.

MSC:

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
05C45 Eulerian and Hamiltonian graphs
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68R10 Graph theory (including graph drawing) in computer science
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
92D20 Protein sequences, DNA sequences

Software:

Stony Brook
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Rothemund, P. W., Design of DNA origami, (Proceedings of the 2005 IEEE/ACM International Conference on Computer-Aided Design (2005), IEEE Computer Society), 471-478
[2] Rothemund, P. W., Folding DNA to create nanoscale shapes and patterns, Nature, 440, 7082, 297-302 (2006)
[3] Chen, J.; Seeman, N. C., Synthesis from DNA of a molecule with the connectivity of a cube, Nature, 350, 6319, 631-633 (1991)
[4] Sa-Ardyen, P.; Jonoska, N.; Seeman, N. C., Self-assembling DNA graphs, (DNA Computing (2003), Springer), 1-9 · Zbl 1026.68560
[5] Sa-Ardyen, P.; Jonoska, N.; Seeman, N. C., The construction of graphs whose edges are DNA helix axes, J. Am. Chem. Soc., 126, 6648-6657 (2004)
[6] Andersen, E. S.; Dong, M.; Nielsen, M. M.; Jahn, K.; Subramani, R.; Mamdouh, W.; Golas, M. M.; Sander, B.; Stark, H.; Oliveira, C. L., Self-assembly of a nanoscale DNA box with a controllable lid, Nature, 459, 7243, 73-76 (2009)
[7] Gu, H.; Chao, J.; Xiao, S.-J.; Seeman, N. C., Dynamic patterning programmed by DNA tiles captured on a DNA origami substrate, Nat. Nanotechnol., 4, 4, 245-248 (2009)
[8] Tørring, T.; Voigt, N. V.; Nangreave, J.; Yan, H.; Gothelf, K. V., DNA origami: a quantum leap for self-assembly of complex structures, Chem. Soc. Rev., 40, 12, 5636-5646 (2011)
[9] Iinuma, R.; Ke, Y.; Jungmann, R.; Schlichthaerle, T.; Woehrstein, J. B.; Yin, P., Polyhedra self-assembled from DNA tripods and characterized with 3d DNA-PAINT, Science, 344, 6179, 65-69 (2014)
[10] 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)
[11] Zhang, Y.; Seeman, N. C., Construction of a DNA-truncated octahedron, J. Amer. Chem. Soc., 116, 5, 1661-1669 (1994)
[12] 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)
[13] 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)
[14] 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)
[15] 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) · Zbl 1163.68328
[16] Ellis-Monaghan, J. A.; McDowell, A.; Moffatt, I.; Pangborn, G., DNA origami and the complexity of Eulerian circuits with turning costs, Nat. Comput., 1-13 (2014)
[17] Högberg, B.; Liedl, T.; Shih, W. M., Folding DNA origami from a double-stranded source of scaffold, J. Am. Chem. Soc., 131, 26, 9154-9155 (2009)
[18] Edmonds, J., Maximum matching and a polyhedron with 0, l-vertices, J. Res. Natl. Bur. Stand. B, 69, 125-130 (1965) · Zbl 0141.21802
[19] Skiena, S., The Stony Brook Algorithm Repository, (accessed 08 March 2016)
[21] Seeman, N. C., Nucleic acid junctions and lattices, J. Theoret. Biol., 99, 2, 237-247 (1982)
[22] Wang, Y.; Mueller, J. E.; Kemper, B.; Seeman, N. C., Assembly and characterization of five-arm and six-arm DNA branched junctions, Biochemistry, 30, 23, 5667-5674 (1991)
[23] Hagerman, P. J., Flexibility of DNA, Annu. Rev. Biophys. Biophys. Chem., 17, 1, 265-286 (1988)
[24] Dietz, H.; Douglas, S. M.; Shih, W. M., Folding DNA into twisted and curved nanoscale shapes, Science, 325, 5941, 725-730 (2009)
[26] Held, M.; Karp, R. M., A dynamic programming approach to sequencing problems, J. Soc. Ind. Appl. Math., 196-210 (1962) · Zbl 0106.14103
[27] Bellman, R., Dynamic programming treatment of the travelling salesman problem, J. ACM, 9, 1, 61-63 (1962) · Zbl 0106.14102
[28] Seeman, N. C., The design of single-stranded nucleic acid knots, Mol. Eng., 2, 3, 297-307 (1992)
[29] Adams, C. C., The Knot Book (1994), American Mathematical Society · Zbl 0840.57001
[30] Hass, J.; Lagarias, J. C.; Pippenger, N., The computational complexity of knot and link problems, J. ACM, 46, 2, 185-211 (1999) · Zbl 1065.68667
[31] Kronheimer, P. B.; Mrowka, T. S., Khovanov homology is an unknot-detector, Publ. Math. Inst. Hautes Études Sci., 113, 1, 97-208 (2011) · Zbl 1241.57017
[32] Jaeger, F.; Vertigan, D. L.; Welsh, D. J., On the computational complexity of the Jones and Tutte polynomials, Math. Proc. Cambridge, 108, 01, 35-53 (1990) · Zbl 0747.57006
[34] Seeman, N. C., Synthetic single-stranded DNA topology, (Buck, D.; Flapan, E., Applications of Knot Theory. Applications of Knot Theory, 4-5 January 2008. Applications of Knot Theory. Applications of Knot Theory, 4-5 January 2008, Proc. Sympos. Appl. Math., vol. 66 (2009), American Mathematical Society: American Mathematical Society San Diego, CA), 121-153 · Zbl 1178.92017
[35] Baas, N. A.; Seeman, N. C.; Stacey, A., Synthesising topological links, J. Math. Chem., 53, 1, 183-199 (2015) · Zbl 1307.92305
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.