  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.
