The PATS Problem: Search Methods and Reliability

Näytä kaikki kuvailutiedot

Julkaisun nimi: The PATS Problem: Search Methods and Reliability
Tekijä: Lempiäinen, Tuomo
Muu tekijä: Helsingin yliopisto, Matemaattis-luonnontieteellinen tiedekunta, Tietojenkäsittelytieteen laitos
Opinnäytteen taso: pro gradu -tutkielmat
Tiivistelmä: 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.
URI: URN:NBN:fi-fe2017112251141
Päiväys: 2015
Oppiaine: Computer science


Latausmäärä yhteensä: Ladataan...

Tiedosto(t) Koko Formaatti Näytä
tlempiainenminorthesis.pdf 784.3KB PDF Avaa tiedosto
tlempiainen-minorthesis.pdf 784.3KB PDF Avaa tiedosto

Viite kuuluu kokoelmiin:

Näytä kaikki kuvailutiedot