Akcelerace algoritmů pro hledání palindromu a opakujících se struktur

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.

Grantor dc:publisher

Vysoké učení technické v Brně. Fakulta informačních technologií

Author dc:creator

• Voženílek, Jan

Advisor dc:contributor.advisor

• Martínek, Tomáš

• Hledání přibližných palindromů
• hardwarová akcelerace
• VHDL
• FPGA.
• Approximate palindrome detection
• hardware acceleration

Statement dc:rights

• Standardní licenční smlouva - přístup k plnému textu bez omezení

Language dc:language.iso

cs

Dc Identifier Other

34540

OAI identifier oai:identifier

oai:dspace.vut.cz:11012/54337