Original title: Akcelerace algoritmů pro hledání palindromu a opakujících se struktur
Translated title: Acceleration of Methods for Searching Palindroms and Repetitive Structures
Authors: Voženílek, Jan ; Kořenek, Jan (referee) ; Martínek, Tomáš (advisor)
Document type: Master’s theses
Year: 2010
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [cze] [eng]
Veškerá genetická informace živých organismů je uložena v DNA. Zkoumání její struktury a funkce představuje důležitou oblast výzkumu moderní biologie. Jednou ze zajímavých struktur, vyskytujících se v sekvencích DNA, jsou také palindromy. Na základě jejich výzkumu se předpokládá, že hrají důležitou roli při interpretaci informace uložené v DNA, jelikož se často vyskytují v okolí důležitých genů. Jejich hledání je složitější díky výskytu mutací (změn v posloupnosti prvků DNA), což zvyšuje časovou složitost algoritmů. Proto má smysl zabývat se jejich paralelizací a akcelerací. Rozborem metod pro hledání palindromů a návrhem akcelerační architektury se zabývá tato práce. Výpočet pomocí hardwarové jednotky implementované v čipu FPGA na kartě ml555 může být až 6 667krát rychlejší oproti nejlepšímu známému softwarovému řešení využívajícímu sufixová pole. Genetic information of all living organisms is stored in DNA. Exploring of its structure and function represents an important area of research in modern biology. One of the interesting structures occurring in DNA are palindromes. Based on the research they are expected to play an important role in interpreting the information stored in DNA, because they are often observed near important genes. Palindromes searching is complicated by the presence of mutations (changes in sequences of DNA elements), which increases the time complexity of algorithms. Therefore it is reasonable to study their parallelization and acceleration. The objective of this work is a study of palindromes searching methods and acceleration architecture design. The hardware unit implemented in a chip with FPGA technology placed on ml555 board can speed up the calculation up to 6 667 times in comparison with the best-known software method relying on suffix arrays.
Keywords: Approximate palindrome detection; FPGA.; hardware acceleration; VHDL; FPGA.; hardwarová akcelerace; Hledání přibližných palindromů; VHDL

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/54337

Permalink: http://www.nusl.cz/ntk/nusl-543379


The record appears in these collections:
Universities and colleges > Public universities > Brno University of Technology
Academic theses (ETDs) > Master’s theses