ACO The ACO Seminar (2014–2015)

Mar. 26, 3:30pm, Wean 8220
Andrew McDowell, Carnegie Mellon University
DNA origami and the complexity of Eulerian circuits with turning costs


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.

Back to the ACO home page