We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
DNA origami and the complexity of Eulerian circuits with turning costs.
- Authors
Ellis-Monaghan, Joanna; McDowell, Andrew; Moffatt, Iain; Pangborn, Greta
- Abstract
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.
- Subjects
DNA analysis; HAMILTON'S equations; EULERIAN graphs; MOLECULAR recognition; COMPUTATIONAL complexity
- Publication
Natural Computing, 2015, Vol 14, Issue 3, p491
- ISSN
1567-7818
- Publication type
Article
- DOI
10.1007/s11047-014-9457-2