{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,20]],"date-time":"2025-10-20T10:18:41Z","timestamp":1760955521162},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2014,9,5]],"date-time":"2014-09-05T00:00:00Z","timestamp":1409875200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat Comput"],"published-print":{"date-parts":[[2015,9]]},"DOI":"10.1007\/s11047-014-9457-2","type":"journal-article","created":{"date-parts":[[2014,9,4]],"date-time":"2014-09-04T19:50:10Z","timestamp":1409860210000},"page":"491-503","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["DNA origami and the complexity of Eulerian circuits with turning costs"],"prefix":"10.1007","volume":"14","author":[{"given":"Joanna A.","family":"Ellis-Monaghan","sequence":"first","affiliation":[]},{"given":"Andrew","family":"McDowell","sequence":"additional","affiliation":[]},{"given":"Iain","family":"Moffatt","sequence":"additional","affiliation":[]},{"given":"Greta","family":"Pangborn","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,9,5]]},"reference":[{"key":"9457_CR2","doi-asserted-by":"crossref","first-page":"1021","DOI":"10.1126\/science.7973651","volume":"266","author":"L Adelman","year":"1994","unstructured":"Adelman L (1994) Molecular computation of solutions to combinatorial problems. Science 266:1021\u20131024","journal-title":"Science"},{"issue":"3","key":"9457_CR4","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0166-218X(95)80001-K","volume":"59","author":"LD Andersen","year":"1995","unstructured":"Andersen LD, Fleischner H (1995) The NP-completeness of finding A-trails in Eulerian graphs and of finding spanning trees in hypergraphs. Discret Appl Math 59(3):203\u2013214","journal-title":"Discret Appl Math"},{"issue":"2","key":"9457_CR3","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1006\/jctb.1996.0017","volume":"66","author":"LD Andersen","year":"1996","unstructured":"Andersen LD, Bouchet A, Jackson B (1996) Orthogonal A-trails of 4-regular graphs embedded in surfaces of low genus. J Combin Theory Ser B 66(2):232\u2013246","journal-title":"J Combin Theory Ser B"},{"issue":"2","key":"9457_CR5","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/S0166-218X(97)00141-8","volume":"85","author":"LD Andersen","year":"1998","unstructured":"Andersen LD, Fleischner H, Regner S (1998) Algorithms and outerplanar conditions for A-trails in plane Eulerian graphs. Discret Appl Math 85(2):99\u2013112","journal-title":"Discret Appl Math"},{"issue":"3","key":"9457_CR1","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1137\/S0097539703434267","volume":"35","author":"E Arkin","year":"2005","unstructured":"Arkin E, Bender M, Demaine E et al (2005) Optimal covering tours with turn costs. SIAM J Comput 35(3):531\u2013566","journal-title":"SIAM J Comput"},{"issue":"1","key":"9457_CR6","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0166-218X(87)90045-X","volume":"18","author":"SW Bent","year":"1987","unstructured":"Bent SW, Manber U (1987) On non-intersecting Eulerian circuits. Discret Appl Math 18(1):87\u201394","journal-title":"Discret Appl Math"},{"key":"9457_CR7","unstructured":"Chartrand G (1964) Graphs and their associated line-graphs. PhD thesis, Michigan State University"},{"key":"9457_CR8","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1038\/350631a0","volume":"350","author":"J Chen","year":"1991","unstructured":"Chen J, Seeman N (1991) Synthesis from DNA of a molecule with the connectivity of a cube. Nature 350:631\u2013633","journal-title":"Nature"},{"key":"9457_CR9","unstructured":"Christofides N (1976) Worst-case analysis of a new heuristic for the travelling salesman problem. Report 388, Graduate School of Industrial Administration, CMU"},{"key":"9457_CR10","doi-asserted-by":"crossref","first-page":"725","DOI":"10.1126\/science.1174251","volume":"325","author":"H Dietz","year":"2009","unstructured":"Dietz H, Douglas S, Shih W (2009) Folding DNA into twisted and curved nanoscale shapes. Science 325:725\u2013730","journal-title":"Science"},{"issue":"2","key":"9457_CR12","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1287\/opre.43.2.231","volume":"43","author":"H Eiselt","year":"1995","unstructured":"Eiselt H, Gendreau M, Laporte G (1995) Arc routing problems, part I: the Chinese postman problem. Oper Res 43(2):231\u2013242","journal-title":"Oper Res"},{"key":"9457_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4614-6971-1","volume-title":"Graphs on surfaces: dualities, Polynomials, and Knots","author":"J Ellis-Monaghan","year":"2013","unstructured":"Ellis-Monaghan J, Moffatt I (2013) Graphs on surfaces: dualities, Polynomials, and Knots. Springer, Berlin"},{"key":"9457_CR15","volume-title":"Discrete and topological models in molecular biology","author":"J Ellis-Monaghan","year":"2013","unstructured":"Ellis-Monaghan J, Pangborn G et al (2013) Minimal tile and bond-edge types for self-assembling DNA graphs. In: Jonoska N, Saito M (eds) Discrete and topological models in molecular biology. Springer, Berlin"},{"key":"9457_CR16","volume-title":"Eulerian graphs and related topics. Volume 45 annals of discrete mathematics part 1","author":"H Fleischner","year":"1990","unstructured":"Fleischner H (1990) Eulerian graphs and related topics. Volume 45 annals of discrete mathematics part 1, vol 1. North-Holland Publishing Co., Amsterdam"},{"key":"9457_CR17","volume-title":"Eulerian graphs and related topics. Volume 50 annals of discrete mathematics Part 1","author":"H Fleischner","year":"1991","unstructured":"Fleischner H (1991) Eulerian graphs and related topics. Volume 50 annals of discrete mathematics Part 1, vol 2. North-Holland Publishing Co., Amsterdam"},{"key":"9457_CR19","volume-title":"Computers and intractability. A guide to the theory of NP-completeness. A series of books in the mathematical sciences","author":"M Garey","year":"1979","unstructured":"Garey M, Johnson D (1979) Computers and intractability. A guide to the theory of NP-completeness. A series of books in the mathematical sciences. W. H. Freeman and Co., San Francisco"},{"key":"9457_CR20","doi-asserted-by":"crossref","first-page":"701","DOI":"10.4153\/CMB-1965-051-3","volume":"8","author":"F Harary","year":"1965","unstructured":"Harary F, Nash-Williams C (1965) On Eulerian and Hamiltonian graphs and line graphs. Canad Math Bull 8:701\u2013709","journal-title":"Canad Math Bull"},{"key":"9457_CR21","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1038\/nature06597","volume":"452","author":"Y He","year":"2008","unstructured":"He Y, Ye T, Su M, Zhuang C, Ribbe A, Jiang W, Mao C (2008) Hierarchical self-assembly of DNA into symmetric supramolecular polyhedral. Nature 452:198\u2013202","journal-title":"Nature"},{"key":"9457_CR22","doi-asserted-by":"crossref","unstructured":"Held M, Karp R (1961) A dynamic programming approach to sequencing problems. In: Proceedings of the 1961 16th ACM national meeting, ACM, 71.201-71.204. ACM, New York, NY","DOI":"10.1145\/800029.808532"},{"issue":"XX","key":"9457_CR23","doi-asserted-by":"crossref","first-page":"9154","DOI":"10.1021\/ja902569x","volume":"131","author":"B Hogberg","year":"2009","unstructured":"Hogberg B, Liedl T, Shih W (2009) Folding DNA origami from a double-stranded source of scaffold. J Am Chem Soc 131(XX):9154\u20139155","journal-title":"J Am Chem Soc"},{"key":"9457_CR26","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1007\/3-540-48017-X_7","volume":"2340","author":"N Jonoska","year":"2002","unstructured":"Jonoska N, Saito M (2002) Boundary components of thickened graphs. Lect Notes Comput Sci 2340:70\u201381","journal-title":"Lect Notes Comput Sci"},{"issue":"XX","key":"9457_CR25","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/S0303-2647(99)00041-6","volume":"52","author":"N Jonoska","year":"1999","unstructured":"Jonoska N, Karl S, Saito M (1999) Three dimensional DNA structures in computing. BioSystems 52(XX):143\u2013153","journal-title":"BioSystems"},{"issue":"15","key":"9457_CR27","doi-asserted-by":"crossref","first-page":"1448","DOI":"10.1016\/j.tcs.2008.12.004","volume":"410","author":"N Jonoska","year":"2009","unstructured":"Jonoska N, Seeman NC, Wu G (2009) On existence of reporter strands in DNA-based graph structures. Theor Comput Sci 410(15):1448\u20131460","journal-title":"Theor Comput Sci"},{"key":"9457_CR28","volume-title":"Algorithm design","author":"J Kleinberg","year":"2005","unstructured":"Kleinberg J, Tardos E (2005) Algorithm design. Addison-Wesley Longman Publishing Co., Inc, Boston"},{"key":"9457_CR29","first-page":"219","volume":"1966","author":"A Kotzig","year":"1968","unstructured":"Kotzig A (1968) Eulerian lines in finite 4-valent graphs and their transformations. Theory Gr 1966:219\u2013230","journal-title":"Theory Gr"},{"key":"9457_CR31","volume-title":"The traveling salesman problem: a guided tour of combinatorial optimization","year":"1985","unstructured":"Lawler EL, Lenstra JK, Rinnooy Kan AHG, Shmoys DB (eds) (1985) The traveling salesman problem: a guided tour of combinatorial optimization. Wiley, New York"},{"key":"9457_CR32","first-page":"451","volume-title":"Eulerian circuits of 4-valent graphs embedded in surfaces. Algebraic methods in graph theory, szeged, 1978, colloquia mathematics societatis Janos Bolyai","author":"M Las Vergnas","year":"1981","unstructured":"Las Vergnas M (1981) Eulerian circuits of 4-valent graphs embedded in surfaces. Algebraic methods in graph theory, szeged, 1978, colloquia mathematics societatis Janos Bolyai, vol 25. North Holland, Amsterdam, pp 451\u2013477"},{"issue":"XX","key":"9457_CR33","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1016\/S1369-7021(03)01130-1","volume":"6","author":"D Luo","year":"2003","unstructured":"Luo D (2003) The road from biology to materials. Mater Today 6(XX):38\u201343","journal-title":"Mater Today"},{"issue":"5","key":"9457_CR34","doi-asserted-by":"crossref","first-page":"608","DOI":"10.1016\/j.cbpa.2010.06.182","volume":"14","author":"J Nangreave","year":"2010","unstructured":"Nangreave J, Han D, Liu Y, Yan H (2010) DNA origami: a history and current perspective. Curr Opin Chem Biol 14(5):608\u2013615","journal-title":"Curr Opin Chem Biol"},{"key":"9457_CR35","unstructured":"New Graph Theory from and for Nanoconstruct Design Strategies (2012) https:\/\/sites.google.com\/site\/nanoselfassembly Cited 29 Aug 2013"},{"key":"9457_CR36","doi-asserted-by":"crossref","first-page":"763","DOI":"10.1038\/nnano.2011.187","volume":"6","author":"AV Pinheiro","year":"2011","unstructured":"Pinheiro AV, Han D, Shih W, Yan H (2011) Challenges and opportunities for structural DNA nanotechnology. Nature Nanotechnology 6:763\u201372","journal-title":"Nature Nanotechnology"},{"issue":"3","key":"9457_CR39","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/0012-365X(91)90119-M","volume":"89","author":"RB Richter","year":"1991","unstructured":"Richter RB (1991) Spanning trees, Euler tours, medial graphs, left-right paths and cycle spaces. Discret Math 89(3):261\u2013268","journal-title":"Discret Math"},{"key":"9457_CR40","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1038\/nature04586","volume":"440","author":"P Rothemund","year":"2006","unstructured":"Rothemund P (2006) Folding DNA to create nanoscale shapes and patterns. Nature 440:297\u2013302","journal-title":"Nature"},{"key":"9457_CR41","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1038\/464158a","volume":"464","author":"K Sanderson","year":"2010","unstructured":"Sanderson K (2010) Bioengineering: what to make with DNA origami. Nature 464:158\u2013159","journal-title":"Nature"},{"key":"9457_CR44","doi-asserted-by":"crossref","first-page":"618","DOI":"10.1038\/nature02307","volume":"427","author":"W Shih","year":"2004","unstructured":"Shih W, Quispe J, Joyce G (2004) A 1.7 kilobase single-stranded DNA that folds into a nanoscale octahedron. Nature 427:618\u2013621","journal-title":"Nature"},{"issue":"1\u20133","key":"9457_CR46","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1016\/S0012-365X(01)00061-9","volume":"244","author":"A \u017ditnik","year":"2002","unstructured":"\u017ditnik A (2002) Plane graphs with Eulerian Petrie walks. Discret Math 244(1\u20133):539\u2013549","journal-title":"Discret Math"},{"key":"9457_CR47","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1038\/nature08274","volume":"461","author":"J Zheng","year":"2009","unstructured":"Zheng J, Birktoft J, Chen Y, Wang T, Sha R, Constantinou P, Ginell S, Mao C, Seeman N (2009) From molecular to macroscopic via the rational design of a self-assembled 3D DNA crystal. Nature 461:74\u201377","journal-title":"Nature"},{"issue":"5","key":"9457_CR48","doi-asserted-by":"crossref","first-page":"1661","DOI":"10.1021\/ja00084a006","volume":"116","author":"Y Zhang","year":"1994","unstructured":"Zhang Y, Seeman N (1994) Construction of a DNA-truncated octahedron. J Am Chem Soc 116(5):1661\u20131669","journal-title":"J Am Chem Soc"}],"container-title":["Natural Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-014-9457-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11047-014-9457-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-014-9457-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,1]],"date-time":"2019-06-01T03:46:11Z","timestamp":1559360771000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11047-014-9457-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,9,5]]},"references-count":38,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,9]]}},"alternative-id":["9457"],"URL":"https:\/\/doi.org\/10.1007\/s11047-014-9457-2","relation":{},"ISSN":["1567-7818","1572-9796"],"issn-type":[{"value":"1567-7818","type":"print"},{"value":"1572-9796","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,9,5]]}}}