The PATS Problem : Search Methods and Reliability

Show full item record

Title: The PATS Problem : Search Methods and Reliability
Author: Lempiäinen, Tuomo
Other contributor: Helsingin yliopisto, Matemaattis-luonnontieteellinen tiedekunta, Tietojenkäsittelytieteen laitos
University of Helsinki, Faculty of Science, Department of Computer Science
Helsingfors universitet, Matematisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap
Publisher: Helsingfors universitet
Date: 2015
Language: eng
Thesis level: master's thesis
Discipline: Computer science
Abstract: This work studies an NP-hard combinatorial optimisation problem, the Pattern self-Assembly Tile set Synthesis (PATS) problem, which stems from the field of DNA self-assembly. In this problem, we are given a coloured rectangular pattern as input, and the task is to find a minimal set of unit square tiles that self-assemble that pattern in the abstract Tile Assembly Model (aTAM). We present two new search methods for the PATS problem: a heuristic algorithm that conducts a search in the lattice of partitions of the input grid, and a declarative approach that uses the Answer Set Programming (ASP) paradigm. The former is based on a previous algorithm by Göös and Orponen (DNA 2010), and performs better in finding relatively small solutions even for quite large input patterns. The latter proves to find the optimal solution quickly in cases where it is small. In addition to the search procedures, we develop a method for estimating the reliability of solutions to the PATS problem from a stochastic point of view. It turns out that tile sets found by our procedures, as well as small tile sets in general, have a higher probability of error-free assembly compared to those that can be found by previous methods.

Files in this item

Total number of downloads: Loading...

Files Size Format View
tlempiainenminorthesis.pdf 784.3Kb PDF View/Open
tlempiainen-minorthesis.pdf 784.3Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record