Hodnocení podobnosti biologických sekvencí s využitím technologie FPGA

Evaluation of biological sequence similarity using FPGA technology

dizertace

čeština

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.

Understanding structure and function of DNA sequences represents one of the most important goals in area of modern biology research. However, algorithms for DNA analysis are usually complicated by mutations caused by an evolution process, which usually occur in form of character insertion, deletion and substitution.  With respect to these defects, the time complexity of the algorithms grows and limits their practical usage. This problem becomes more significant in the light of next-generation sequencing technologies, which are able to generate billions of bases per minute at the cost of several hundreds of dollars.  Techniques for an acceleration of the key and frequently used operations using specific circuits bring a certain expectation into this area.  Therefore, the first part of this thesis is dedicated to hardware acceleration of selected algorithms for DNA sequence analysis, especially algorithms for approximate palindrome and approximate tandem repeat detection. In comparison to previous approaches, the novel designed circuits are configurable using several parameters and capable to detect all types of defects (character insertion, deletion and substitution). Mapping of these architectures into the FPGA technology shows speedup in orders of thousands in comparison to the best known algorithms, which are implemented in the software and use suffix array structure. Despite of huge performance of these novel as well as existing circuits, they are not used in wide range of real word applications.  The main reason lies often in variability of input tasks that leads to change of architecture parameters and adaptation of its dimensions with respect to the target platform properties. These modifications usually require an intervention of experienced designer, and thus complicate their usage in real word applications.  The second part of this thesis is therefore dedicated to design and implementation of novel methods for automated mapping of circuits into the chips with FPGA technology.  At first, the problem of mapping is investigated into the detail and formally defined using a parametrized architecture model. Based on this formal model, a novel mapping technique is designed. In comparison to previous approaches, this technique is capable to find the optimal dimensions of the resulting circuit and it does not limit description of the architecture parts to linear functions only. Finally, the proposed method is evaluated on three examples of architectures for DNA sequence analysis. The parametric model is build for each example and the method is applied to find the optimal dimensions of the circuits with respect to limited I/O bandwidth and limited amount of resources inside the chip.

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

Approximate string matching, approximate palindrome detection, approximate tandem repeat detection, systolic array, programmable hardware, FPGA technology, nested loops mapping, design space exploration, high-level synthesis

MARTÍNEK, T.

6. 12. 2010

Ústav počítačových systémů FIT VUT v Brně

Brno

125