Original title:
Interaktivní simulátor DNA výpočtu
Translated title:
An Interactive DNA Computing Simulator
Authors:
Kovács, Martin ; Petrlík, Jiří (referee) ; Bidlo, Michal (advisor) Document type: Bachelor's theses
Year:
2014
Language:
cze Publisher:
Vysoké učení technické v Brně. Fakulta informačních technologií Abstract:
[cze][eng]
Tato práce je zaměřena na shrnutí biologických operací nad DNA a jejich nasazení ve výpočtu složitých matematických problémů. Ukázkovým příkladem, jehož řešení je v práci demonstrováno, je problém hamiltonovské cesty grafem, také znám jako problém obchodního cestujícího. Při řešení tohoto problému budou popsány použité operace nad DNA a postup, který poprvé představil Leonard Adleman. Jeho práci je možné považovat za první experiment v oboru, který je teď známý jako DNA počítání. Cílem této bakalářské práce je implementovat interaktivní simulační program (založený na principech a formálním modelu Adlemanovy práce) pro řešení hamiltonovské cesty grafem a zhodnotit jeho možnosti vzhledem na prostorovou složitost při různých instancích problému obchodního cestujícího.
The aim of this work is to summarize the basic principles of operations performed over DNA molecules and to demonstrate their usage in solving some hard mathematical problems. In particular, the Hamiltonian Path Problem -- HPP (also known as the Traveling Salesman Problem) will be considered as a case study. A fundamental approach introduced by Leonard Adleman will be desctribed to solve the HPP using the DNA operations. His work may be considered as the first experiment in the area that is currently known as DNA computing. The goal of this bachelor thesis is to implement an interactive software simulator (based on the principles and formal models of Adleman's work) for solving the HPP and to evaluate its abilities with respect to area complexity considering various instances of HPP.
Keywords:
DNA computation; DNA operations; graph; Hamiltonian path; DNA výpočet; graf; hamiltonovská cesta grafem; operace nad DNA
Institution: Brno University of Technology
(web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library. Original record: http://hdl.handle.net/11012/56389