The field of nanotechnology has enabled scientists to perform fascinating engineering manipulations of biological substrates. Systems of DNA are now able to perform algorithmic computations by way of constructing biological modules composed of DNA macromolecules and using laboratory techniques available to biological sciences. The tile assembly model is an established model of biomolecular computing: using properties of DNA macromolecules to define constructions of self-assembling biological systems. The existing tile assembly model uses the concept of DNA tiles conceptually shaped as squares and exposes the tiles to carefully controlled biological conditions. The result is that under this process we can design and create these systems to compute solutions to algorithmic problems. Hexagons are the only two-dimensional regular polygon other than squares that can tile a plane infinitely leaving no space uncovered, where only translations of the initial polygon is allowed. Therefore hexagon-shaped DNA tiles can be defined to cover a planar surface, with the notable difference of six adjacent tiles per position versus the four adjacent neighbours in traditional four sided tiles.
In this thesis, we will define a generalization of the tile assembly model that supports six-sided DNA tiles, in addition to the traditional four sides. We will introduce a problem known as the 0-1 Knapsack problem that is currently unsolved with square tiles. Moreover, a solution to the problem was attempted by tile assembly model researchers, however we show there is an error in their solution. After we analyze their solution and discover the shortcomings of square tiles under those constraints, we then show this fault is not applicable to hexagon tiles. Therefore, we show that the 0-1 Knapsack problem is solvable using hexagon shaped tiles.
| Identifer | oai:union.ndltd.org:MANITOBA/oai:mspace.lib.umanitoba.ca:1993/30147 |
| Date | 06 January 2015 |
| Creators | Sinclair, Andrew |
| Contributors | Domaratzki, Michael (Computer Science), Kocay, William (Computer Science) Padmanabhan, Ranganathan (Mathematics) |
| Source Sets | University of Manitoba Canada |
| Detected Language | English |
Page generated in 0.0019 seconds