Název:
Konstrukce sufixových stromů a jejich využití v bioinformatice
Překlad názvu:
Suffix Trees Construction and Their Use in Bioinformatics
Autoři:
Hlaváček, Pavel ; Čermák, Martin (oponent) ; Martínek, Tomáš (vedoucí práce) Typ dokumentu: Bakalářské práce
Rok:
2011
Jazyk:
cze
Nakladatel: Vysoké učení technické v Brně. Fakulta informačních technologií
Abstrakt: [cze][eng]
Práce se zabývá problematikou implementace sufixových stromů a jejich využití v bioinformatice. Jsou zde uvedeny různé druhy algoritmů pro tvorbu sufixových stromů. Především se zabývá implementací on-line metody pro tvorbu sufixového stromu navrženou E. Ukkonenem a přibližným vyhledáváním podřetězců. To je realizováno za pomoci dynamického programování, upraveného pro využití sufixových stromů. Obě tyto metody jsou popsány pseudokódem a implementovány v příloze práce.
This work discusses problems of suffix trees implementation and their use in bioinformatics. There are given different sorts of algorithms for building suffix trees in this work. In the first place, it deals with the on-line method implementation for building suffix trees, proposed by E. Ukkonen and approximate string matching. That is made by application of dynamic programming principles, adapted for using suffix trees. Both of these methods are described by pseudocode and implemented in a work supplement.
Klíčová slova:
McCreight; odpovídající; online metoda; podřetězce; prefix; přibližný; sufix; Sufixový strom; Ukkonen; řetězec; approximate; matching; McCreight; online; preffix; string; substring; suffix; Suffix tree; Ukkonen
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/55648