On Monday, April 28, 2014, the Departments of Mathematical Sciences, Biology & Biotechnology, and Physics will present a special colloquium given by Jo Ellis-Monaghan of Saint Michael's College and the University of Vermont.
and the Complexity of Eulerian Circuits with Turning Costs
Saint Michael’s College
The University of Vermont
Monday, April 28, 2014
4 -5pm, Kaven Hall 116
In 1994, Adelman gave a proof-of-concept for biomolecular computing by demonstrating a selfassembling DNA tetrahedron and using a biomolecular process to find a Hamilton cycle. Since then, instances of several other classical NP-Hard problems, such as 3-SAT and graph coloring, have been solved through biomolecular computing processes using DNA self-assembly. The first step in such a problem is designing the input, that is, self-assembling a graph out of strands of DNA. One of the most successful recent techniques for self-assembly of graph-theoretical structures from DNA molecules is by origami folding, which involves 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 NPHard. This means that this popular assembly method may not be appropriate for efficient biomolecular computing. We show that the problem may readily be transformed into a Traveling Salesman Problem (TSP), so that the 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 for other purposes (e.g. medical applications).
This is joint work with Andrew McDowell, Iain Moffatt, and Greta Pangborn.
Jointly sponsored by the Departments of Mathematical Sciences, Biology & Biotechnology, and Physics
April 23, 2014