Original title:
Vyhledávání přibližných palindromů v DNA sekvencích
Translated title:
Finding Approximate Palindromes in DNA Sequences
Authors:
Remiáš, Richard ; Burgetová, Ivana (referee) ; Martínek, Tomáš (advisor) Document type: Bachelor's theses
Year:
2010
Language:
cze Publisher:
Vysoké učení technické v Brně. Fakulta informačních technologií Abstract:
[cze][eng]
Práca sa zaoberá problematikou vyhľadávania presných a približných palindrómov. V súvislosti s vyhľadávaním presných palindrómov analyzuje naivný postup vyhľadávania ako aj postupy založené na sufixových stromoch, ktorých konštrukcia je tiež rozobraná. Vyhľadávanie približných palindrómov je realizované za pomoci princípov dynamického programovania. Samotné vyhľadávanie je rozdelené na tri časti: vyhľadanie palindrómov, filtrácia výsledkov a ich rekonštrukcia. Každá časť je popísaná algoritmom a implementovaná programom v prílohe práce.
This work discusses problematics of exact and approximate palindrome searching. In relation with exact palindrome searching, native algorithm and algorithm using suffix trees, which construction is also analyzed, is presented. Approximate palindrome search is implemented with application of dynamic programming principles. The search itself is dividded into three parts: palidnrome search, result filter and reconstruction of palindromes. Each part is described by an algorithm and implemented in a program, contained in attachment.
Keywords:
approximate palindrome; dynamic programming.; exact palindrome; Palindrome; palindrome searching; suffix tree; dynamické programování.; Palindrom; přesný palindrom; přibližný palindrom; sufixový strom; vyhledávání palindromů
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/52995