Mathematical Sciences Seminar - DNA origami and the complexity of Eulerian circuits with turning costs
When:
—
Venue:
Birkbeck Main Building, Malet Street
No booking required
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
Contact name:
Department of Economics, Mathematics and Statistics