The ACO Seminar (2014–2015)

DNA origami is the process of designing artificial DNA strands that assemble themselves into nanoscale structures. The design process for this can be reduced to finding a minimum weight Eulerian circuit in a graph where the costs are assigned to the possible transitions between edges at each vertex. We demonstrate that this problem is, in general, NP-Hard and identify restrictions for which it remains so or for which we demonstrate polynomial time algorithms.

Joint work with Joanna A. Ellis-Monaghan, Iain Moffatt, and Greta Pangborn.