Thesis Details

Hardwarová akcelerace algoritmu pro hledání podobnosti dvou DNA řetězců

Master's Thesis Student: Nosek Ondřej Academic Year: 2006/2007 Supervisor: Martínek Tomáš, doc. Ing., Ph.D.
English title
Hardware Acceleration of Algorithms for Approximate String Matching
Language
Czech
Abstract

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

DNA sequence, RNA, protein sequence, nucleotide amino-acid, codon, triplet, evolution, genes, pairwise alignment, string matching, global alignment, algorithm acceleration, hardware, architecture, FPGA technology, local alignment, Levenshtein distance, Smith-Waterman algorithm, Needleman-Wunsch algorithm, penalty, gaps backtracking, substitution matrix, match score, computing, matching cell, character rule, sequencer.

Department
Department of Computer Systems FIT BUT
Degree Programme
Information Technology, Field of Study Computer Systems and Networks
Files
Status
defended, grade B
Date
19 June 2007
Reviewer
Kořenek Jan, doc. Ing., Ph.D.
Committee
Dvořák Václav, prof. Ing., DrSc. (DCSY FIT BUT), předseda
Janoušek Vladimír, doc. Ing., Ph.D. (DITS FIT BUT), člen
Kotásek Zdeněk, doc. Ing., CSc. (DCSY FIT BUT), člen
Krejčíček Jaromír, prof. Ing., CSc. (UNOB), člen
Křena Bohuslav, Ing., Ph.D. (DITS FIT BUT), člen
Matoušek Petr, doc. Ing., Ph.D., M.A. (DIFS FIT BUT), člen
Citation
NOSEK, Ondřej. Hardwarová akcelerace algoritmu pro hledání podobnosti dvou DNA řetězců. Brno, 2007. Master's Thesis. Brno University of Technology, Faculty of Information Technology. 2007-06-19. Supervised by Martínek Tomáš. Available from: https://www.fit.vut.cz/study/thesis/4742/
BibTeX 
@mastersthesis{FITMT4742,
    author = "Ond\v{r}ej Nosek",
    type = "Master's thesis",
    title = "Hardwarov\'{a} akcelerace algoritmu pro hled\'{a}n\'{i} podobnosti dvou DNA \v{r}et\v{e}zc\r{u}",
    school = "Brno University of Technology, Faculty of Information Technology",
    year = 2007,
    location = "Brno, CZ",
    language = "czech",
    url = "https://www.fit.vut.cz/study/thesis/4742/"
}

Theses

Back to top