Original title: Implementace algoritmu pro hledání podobností DNA řetězců v FPGA
Translated title: Approximate String Matching Algorithm Implementation in FPGA
Authors: Pařenica, Martin ; Martínek, Tomáš (referee) ; Fučík, Otto (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]
Tato práce popisuje způsoby porovnání nukleotidových řetězců s využitím párového a vícenásobného porovnání. V práci jsou popsány algoritmy párového porovnávání pro hledání nad daty v databázích a nebo algoritmy využívající dynamické programování. Dále jsou popsány způsoby vícenásobného porovnání. Mezi základními algoritmy je uvedeno dynamickým programováním a nebo algoritmy, které s využitím určité míry nepřesnosti postupně sestavují porovnání. Teoretickou část práce uzavírá popis technologie FPGA. Další část práce, praktická část, je věnována implementaci jednoho z vícenásobných algoritmů. Závěrečná část shrnuje vlastnosti vybraného algoritmu. This paper describes sequence alignment algorithms of nucleotide sequences. There are described pairwise alignment algorithms using database search or dynamic programming. Then in the paper is description of dynamic programming for multiple sequences and algorithm that builds phylogenetic trees. At the end of the first part of the paper is the description of technology FPGA. In the second part that is more practical is described implemntation of the choosen one algorithm. This part includes also examples of some multiple alignments.
Keywords: BLAST; CLUSTAL; database search; DNA; dynamic programming; FASTA; FPGA.; multiple alignment; Needleman-Wunsch; pairwise alignment; phylogenetic tree; Smith-Waterman; BLAST; CLUSTAL; DNA; dynamické programování; FASTA; FPGA.; fylogenetické stromy; Needleman-Wunsch; prohledávání databází; párové porovnání; Smith-Waterman; vícenásobné porovnání

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

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


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