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

Abstract:

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