Login | Register

DNA Computation of Solutions to Edge-Matching Puzzles


DNA Computation of Solutions to Edge-Matching Puzzles

Atiia, Ali A ORCID: https://orcid.org/0000-0002-3116-7415 (2011) DNA Computation of Solutions to Edge-Matching Puzzles. Masters thesis, Concordia University.

[thumbnail of Atiia_2011.pdf]
Text (application/pdf)
Atiia_2011.pdf - Accepted Version


The resilient, ancient, and fine-tuned DNA (deoxyribonucleic acid) has inspired many
researchers to harness its power for material purposes. In this work, we use synthesized DNA
strands to compute the solution to an instance of edge-matching puzzles (EMP), where the
challenge is to pack a collection of edge-coloured square tiles on a square board such that all
adjacent edges match in colour. We encode tiles with DNA strands and make use of structural,
chemical and enzymatic properties of DNA to effectively carry out a brute-force search of the
solution to the puzzle. The solution ultimately results as a 2-dimensional DNA lattice encoding
the position and orientation of each tile on the solution board. Our approach has been to
represent a tile as the union of two half-tiles. This conceptual representation allows for the use
of a supremely powerful heuristic: polymerase chain reaction (PCR), which can be inserted at
any step of the protocol to selectively amplify certain strands to exponential quantities. Our
abstract formalization of half-tiles and the DNA protocol we use to manipulate them have
relevance in three ways. First, by solving an instance of the (NP-Complete) EMP problem we
make precise characterizations of the processing power of DNA Computing. Second, the 2-
dimensional self-assembly of half-tiles is Turing-complete.
Thirdly, the 2-dimensional self-
assembly of half-tiles can serve as a PCR-powered model for massive nano-scale fabrication of 2-
dimensional DNA nano-shapes.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (Masters)
Authors:Atiia, Ali A
Institution:Concordia University
Degree Name:M. Comp. Sc.
Program:Computer Science
Date:March 2011
Thesis Supervisor(s):Kharma, Nawwaf and Suen, C.
Keywords:DNA computation molecular computing nanotechnology tiling tiles wang np-complete complexity
ID Code:982709
Deposited By: Ali A Atiia
Deposited On:12 Sep 2017 15:00
Last Modified:18 Jan 2018 17:55
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top