Original title: Hardwarová akcelerace algoritmu pro hledání podobnosti dvou DNA řetězců
Translated title: Hardware Acceleration of Algorithms for Approximate String Matching
Authors: Nosek, Ondřej ; Kořenek, Jan (referee) ; Martínek, Tomáš (advisor)
Document type: Master’s theses
Year: 2007
Language: cze
Publisher: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstract: [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.
Keywords: 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; 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.

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

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


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