aalto1 untyped-item.component.html
Combinatorial algorithms for the design of nanoscale systems
Loading...
URL
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu |
Master's thesis
Authors
Mohammed, Abdulmelik
Date
Department
Major/Subject
Mcode
T-79
Degree programme
Language
en
Pages
72 s.
Series
Abstract
Over the past 30 years, DNA, with its exquisitely specific Watson-Crick base pairing rules, has found a novel use as a nanoscale construction material in DNA nanotechnology. DNA origami is a popular recent technique in DNA nanotechnology for the design and synthesis of DNA nanoscale shapes and patterns. DNA origami operates by the folding of a single long strand of DNA called a scaffold with the help of numerous shorter strands of DNA called staples. Recently, DNA origami design for polyhedral beam-frameworks has been proposed where a scaffold strand is conceptually routed over the beams of a polyhedron so that complementary strands potentially fold the scaffold to the framework in a solution.
In this work, we modelled the problem of finding a scaffold routing path for polyhedral frameworks in graph-theoretic terms whereby the routing path was found to coincide with a specific type of Eulerian trail, called an A-trail, on the polyhedral skeleton. We studied the complexity of deciding whether an A-trail exists with an emphasis on rigid triangular frameworks or equivalently on plane triangulations. While the decision problem was found to be NP-complete in general, we learned that Eulerian triangulations always have A-trails if a long standing conjecture by Barnette on the Hamiltonicity of bipartite cubic polyhedral graphs holds.
Given the general NP-completeness result, we developed a backtracking search algorithm for finding A-trails. To improve the backtrack search; we introduced an enumeration heuristic, tuned in particular to Eulerian triangulations, to schedule the nodes in the search tree. The algorithm, guided by the heuristic, efficiently found A-trails for a family of Eulerian triangulations as well as a family of braced grid graphs. Furthermore, we implemented a software package, BScOR (Beam Scaffolded-Origami Routing), which generates an A-trail, or equivalently a scaffold routing path, given a three-dimensional object description in a Polygon File Format.