DNA origami and the complexity of Eulerian circuits with turning costs

详细信息    查看全文

• 作者：Joanna A. Ellis-Monaghan ; Andrew McDowell ; Iain Moffatt…
• 关键词：DNA origami ; DNA self ; assembly ; Turning cost ; Eulerian circuit ; Hamiltonian cycle ; Threading strand ; Biomolecular computing ; Mill routing ; Computational complexity ; A ; trails ; 92E10 ; 05C45 ; 05C85
• 刊名：Natural Computing
• 出版年：2015
• 出版时间：September 2015
• 年：2015
• 卷：14
• 期：3
• 页码：491-503
• 全文大小：627 KB
• 参考文献：Adelman L (1994) Molecular computation of solutions to combinatorial problems. Science 266:1021鈥?024CrossRef
  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鈥?14MathSciNet CrossRef MATH
  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鈥?46MathSciNet CrossRef MATH
  Andersen LD, Fleischner H, Regner S (1998) Algorithms and outerplanar conditions for A-trails in plane Eulerian graphs. Discret Appl Math 85(2):99鈥?12MathSciNet CrossRef MATH
  Arkin E, Bender M, Demaine E et al (2005) Optimal covering tours with turn costs. SIAM J Comput 35(3):531鈥?66MathSciNet CrossRef MATH
  Bent SW, Manber U (1987) On non-intersecting Eulerian circuits. Discret Appl Math 18(1):87鈥?4MathSciNet CrossRef MATH
  Chartrand G (1964) Graphs and their associated line-graphs. PhD thesis, Michigan State University
  Chen J, Seeman N (1991) Synthesis from DNA of a molecule with the connectivity of a cube. Nature 350:631鈥?33CrossRef
  Christofides N (1976) Worst-case analysis of a new heuristic for the travelling salesman problem. Report 388, Graduate School of Industrial Administration, CMU
  Dietz H, Douglas S, Shih W (2009) Folding DNA into twisted and curved nanoscale shapes. Science 325:725鈥?30CrossRef
  Eiselt H, Gendreau M, Laporte G (1995) Arc routing problems, part I: the Chinese postman problem. Oper Res 43(2):231鈥?42MathSciNet CrossRef MATH
  Ellis-Monaghan J, Moffatt I (2013) Graphs on surfaces: dualities, Polynomials, and Knots. Springer, BerlinCrossRef
  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
  Fleischner H (1990) Eulerian graphs and related topics. Volume 45 annals of discrete mathematics part 1, vol 1. North-Holland Publishing Co., Amsterdam
  Fleischner H (1991) Eulerian graphs and related topics. Volume 50 annals of discrete mathematics Part 1, vol 2. North-Holland Publishing Co., Amsterdam
  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
  Harary F, Nash-Williams C (1965) On Eulerian and Hamiltonian graphs and line graphs. Canad Math Bull 8:701鈥?09MathSciNet CrossRef MATH
  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鈥?02CrossRef
  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
  Hogberg B, Liedl T, Shih W (2009) Folding DNA origami from a double-stranded source of scaffold. J Am Chem Soc 131(XX):9154鈥?155CrossRef
  Jonoska N, Saito M (2002) Boundary components of thickened graphs. Lect Notes Comput Sci 2340:70鈥?1MathSciNet CrossRef
  Jonoska N, Karl S, Saito M (1999) Three dimensional DNA structures in computing. BioSystems 52(XX):143鈥?53CrossRef
  Jonoska N, Seeman NC, Wu G (2009) On existence of reporter strands in DNA-based graph structures. Theor Comput Sci 410(15):1448鈥?460MathSciNet CrossRef MATH
  Kleinberg J, Tardos E (2005) Algorithm design. Addison-Wesley Longman Publishing Co., Inc, Boston
  Kotzig A (1968) Eulerian lines in finite 4-valent graphs and their transformations. Theory Gr 1966:219鈥?30MathSciNet
  Lawler EL, Lenstra JK, Rinnooy Kan AHG, Shmoys DB (eds) (1985) The traveling salesman problem: a guided tour of combinatorial optimization. Wiley, New YorkMATH
  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鈥?77
  Luo D (2003) The road from biology to materials. Mater Today 6(XX):38鈥?3CrossRef
  Nangreave J, Han D, Liu Y, Yan H (2010) DNA origami: a history and current perspective. Curr Opin Chem Biol 14(5):608鈥?15CrossRef
  New Graph Theory from and for Nanoconstruct Design Strategies (2012) https://鈥媠ites.鈥媑oogle.鈥媍om/鈥媠ite/鈥媙anoselfassembly鈥?/span> Cited 29 Aug 2013
  Pinheiro AV, Han D, Shih W, Yan H (2011) Challenges and opportunities for structural DNA nanotechnology. Nature Nanotechnology 6:763鈥?2CrossRef
  Richter RB (1991) Spanning trees, Euler tours, medial graphs, left-right paths and cycle spaces. Discret Math 89(3):261鈥?68CrossRef MATH
  Rothemund P (2006) Folding DNA to create nanoscale shapes and patterns. Nature 440:297鈥?02CrossRef
  Sanderson K (2010) Bioengineering: what to make with DNA origami. Nature 464:158鈥?59CrossRef
  Shih W, Quispe J, Joyce G (2004) A 1.7 kilobase single-stranded DNA that folds into a nanoscale octahedron. Nature 427:618鈥?21CrossRef
  沤itnik A (2002) Plane graphs with Eulerian Petrie walks. Discret Math 244(1鈥?):539鈥?49MATH
  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鈥?7CrossRef
  Zhang Y, Seeman N (1994) Construction of a DNA-truncated octahedron. J Am Chem Soc 116(5):1661鈥?669CrossRef
  
• 作者单位：Joanna A. Ellis-Monaghan (1)
  Andrew McDowell (2)
  Iain Moffatt (2)
  Greta Pangborn (3)
  
  1. Department of Mathematics, Saint Michael鈥檚 College, One Winooski Park, Colchester, VT, 05439, USA
  2. Department of Mathematics, Royal Holloway, University of London, Egham, Surrey, TW20 0EX, UK
  3. Department of Computer Science, Saint Michael鈥檚 College, One Winooski Park, Colchester, VT, 05439, USA
  
• 刊物类别：Computer Science
• 刊物主题：Theory of Computation
  Evolutionary Biology
  Processor Architectures
  Artificial Intelligence and Robotics
  Complexity
  
• 出版者：Springer Netherlands
• ISSN：1572-9796

文摘

Building a structure using self-assembly of DNA molecules by origami folding requires finding a route for the scaffolding strand through the desired structure. When the target structure is a 1-complex (or the geometric realization of a graph), an optimal route corresponds to an Eulerian circuit through the graph with minimum turning cost. By showing that it leads to a solution to the 3-SAT problem, we prove that the general problem of finding an optimal route for a scaffolding strand for such structures is NP-hard. We then show that the problem may readily be transformed into a traveling salesman problem (TSP), so that machinery that has been developed for the TSP may be applied to find optimal routes for the scaffolding strand in a DNA origami self-assembly process. We give results for a few special cases, showing for example that the problem remains intractable for graphs with maximum degree 8, but is polynomial time for 4-regular plane graphs if the circuit is restricted to following faces. We conclude with some implications of these results for related problems, such as biomolecular computing and mill routing problems. Keywords DNA origami DNA self-assembly Turning cost Eulerian circuit Hamiltonian cycle Threading strand Biomolecular computing Mill routing Computational complexity A-trails