Mathematics Commons^™

Networks, (K)Nots, Nucleotides, And Nanostructures, Ada Morse

Graduate College Dissertations and Theses

Designing self-assembling DNA nanostructures often requires the identification of a route for a scaffolding strand of DNA through the target structure. When the target structure is modeled as a graph, these scaffolding routes correspond to Eulerian circuits subject to turning restrictions imposed by physical constraints on the strands of DNA. Existence of such Eulerian circuits is an NP-hard problem, which can be approached by adapting solutions to a version of the Traveling Salesperson Problem. However, the author and collaborators have demonstrated that even Eulerian circuits obeying these turning restrictions are not necessarily feasible as scaffolding routes by giving examples of …