Disertace

MARTÍNEK Tomáš. Hodnocení podobnosti biologických sekvencí s využitím technologie FPGA. Brno: Ústav počítačových systémů FIT VUT v Brně, 2010.
Jazyk publikace:čeština
Název publikace:Hodnocení podobnosti biologických sekvencí s využitím technologie FPGA
Název (en):Evaluation of biological sequence similarity using FPGA technology
Strany:125
Místo vydání:Brno, CZ
Rok:2010
Vydavatel:Ústav počítačových systémů FIT VUT v Brně
Klíčová slova
Zarovnání sekvence na základě podobnosti, detekce přibližných palindromů, detekce přibližných tandemových opakování, systolické pole,  programovatelný hardware, technologie FPGA, mapování vnořených smyček, prohledávání stavového prostoru, syntéza obvodů na vyšší úrovni
Anotace
Pochopení struktury a funkce DNA sekvencí tvoří jednu z nejdůležitějších oblastí výzkumu moderní biologie.  Algoritmy pro jejich analýzu jsou však často komplikovány výskytem mutací, které vznikají důsledkem evolučního procesu a projevují se obvykle ve formě záměny, vložení nebo odstranění znaku.  Časová složitost algoritmů vlivem těchto poruch roste a komplikuje jejich praktické použití. Tento problém se dále prohlubuje s příchodem nových technologií sekvenování, které dokáží generovat miliardy bází každou minutu za cenu v řádu stovek dolarů.  Určitou naději do této oblasti přináší techniky urychlování klíčových a často používaných operací s využitím specializovaných obvodů.  První část práce je proto zaměřena na akceleraci vybraných algoritmů z oblasti analýzy DNA sekvencí, zejména algoritmů pro detekci přibližných palindromů a přibližných tandemových opakování. Nově navržené obvody jsou konfigurovatelné řadou parametrů a oproti existujícím přístupům dokáží detekovat všechny typy chyb (záměnu, vložení i odstranění znaku).  Při jejich mapování na technologii FPGA jsou schopny dosáhnout zrychlení v řádu tisíců ve srovnání s nejlepšími známými algoritmy implementovanými na úrovni software a využívajícími struktury sufixového pole.  I přes vysoké zrychlení, které nabízejí tyto nově navržené, ale i existující obvody, nejsou tyto akcelerátory příliš rozšířeny. Jedním z hlavních důvodů je častá variabilita úloh, která vede na změnu parametrů obvodu a přizpůsobení jeho rozměrů s ohledem na vlastnosti použité cílové platformy.  Tyto úpravy obvykle vyžadují zásah ze strany zkušeného návrháře, což komplikuje jejich použitelnost v reálných aplikacích.  Druhá část práce je proto zaměřena na návrh nových metod pro automatizované mapování vytvořených architektur na obvody s technologií FPGA.  Problematika mapování je nejprve podrobně analyzována a formálně definována s využitím modelu parametrizovatelné architektury.  Na základě formálního popisu je následně navržena metoda nová, která je schopna oproti existujícím přístupům nalézt nejen optimální rozměry výsledného obvodu, ale navíc neomezuje popis jednotlivých elementů architektury pouze na lineární funkce.  V závěru práce je navržená metoda zhodnocena na třech příkladech obvodů z oblasti analýzy biologických sekvencí. Pro každý obvod je sestaven jeho parametrizovatelný model a jsou nalezeny jeho optimální rozměry s ohledem na omezenou vstupně/výstupní propustnost a omezené množství zdrojů na čipu.
BibTeX:
@PHDTHESIS{
   author = {Tomáš Martínek},
   title = {Hodnocení podobnosti biologických sekvencí s využitím
	technologie FPGA},
   pages = {125},
   year = {2010},
   location = {Brno, CZ},
   publisher = {Department of Computer Systems FIT BUT},
   language = {czech},
   url = {http://www.fit.vutbr.cz/research/view_pub.php.cs?id=9414}
}

Vaše IPv4 adresa: 54.205.173.252
Přepnout na IPv6 spojení

DNSSEC [dnssec]