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