Název:
Implementace algoritmu pro hledání podobností DNA řetězců v FPGA
Překlad názvu:
Approximate String Matching Algorithm Implementation in FPGA
Autoři:
Pařenica, Martin ; Martínek, Tomáš (oponent) ; Fučík, Otto (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]
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.
Klíčová slova:
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í; BLAST; CLUSTAL; database search; DNA; dynamic programming; FASTA; FPGA.; multiple alignment; Needleman-Wunsch; pairwise alignment; phylogenetic tree; Smith-Waterman
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/53990