Název: Hardwarová akcelerace algoritmu pro hledání podobnosti dvou DNA řetězců
Překlad názvu: Hardware Acceleration of Algorithms for Approximate String Matching
Autoři: Nosek, Ondřej ; Kořenek, Jan (oponent) ; Martínek, Tomáš (vedoucí práce)
Typ dokumentu: Diplomové práce
Rok: 2007
Jazyk: cze
Nakladatel: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstrakt: [cze] [eng]
Metody pro zarovnání různých typů bioinformatických sekvencí jsou klíčovou součástí výzkumu v této oblasti. Úlohy jsou časově velmi náročné, a proto má smysl vytvořit hardwarovou platformu pro urychlení těchto výpoětů. Cílem této práce je navržení obecné architektury založené na FPGA technologii, která dokáže pracovat s několika různými druhy sekvencí. Metody, které bude navržená akcelerační karta používat budou především dynamické algoritmy Needleman-Wunsch a Smith-Waterman. Methods for aproximate string matching of various sequences used in bioinformatics are crucial part of development in this branch. Tasks are of very large time complexity and therefore we want create a hardware platform for acceleration of these computations. Goal of this work is to design a generalized architecture based on FPGA technology, which can work with various types of sequences. Designed acceleration card will use especially dynamic algorithms like Needleman-Wunsch and Smith-Waterman.
Klíčová slova: akcelerace algoritmu; algoritmus; aminokyselina; architektura; DNA řetězec; evoluce; FPGA; geny; globální metoda; hardware; kodón; Levenshteinova vzdálenost; lokální metoda; mezery; Needleman-Wunsch; nukleotid; pokuta; porovnávací buňka; porovnávací pravidla; porovnávání řetězc; proteinový řetězec; RNA; skóre podobnosti; Smith-Waterman; substituční matice; triplet; výpočet; zarovnání; zpětný průchod; řídící obvod.; algorithm acceleration; architecture; character rule; codon; computing; DNA sequence; evolution; FPGA technology; gaps backtracking; genes; global alignment; hardware; Levenshtein distance; local alignment; match score; matching cell; Needleman-Wunsch algorithm; nucleotide amino-acid; pairwise alignment; penalty; protein sequence; RNA; sequencer.; Smith-Waterman algorithm; string matching; substitution matrix; triplet

Instituce: Vysoké učení technické v Brně (web)
Informace o dostupnosti dokumentu: Plný text je dostupný v Digitální knihovně VUT.
Původní záznam: http://hdl.handle.net/11012/54025

Trvalý odkaz NUŠL: http://www.nusl.cz/ntk/nusl-545823


Záznam je zařazen do těchto sbírek:
Školství > Veřejné vysoké školy > Vysoké učení technické v Brně
Vysokoškolské kvalifikační práce > Diplomové práce