Algorithms, Combinatorics and Optimization Seminar Andrew McDowell
Carnegie Mellon University
Title: 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.

Date: Thursday, March 26, 2015
Time: 3:30 pm
Location: Wean Hall 8220
Submitted by:  Bukh