Original title:
Konstrukce sufixových stromů a jejich využití v bioinformatice
Translated title:
Suffix Trees Construction and Their Use in Bioinformatics
Authors:
Hlaváček, Pavel ; Čermák, Martin (referee) ; Martínek, Tomáš (advisor) Document type: Bachelor's theses
Year:
2011
Language:
cze Publisher:
Vysoké učení technické v Brně. Fakulta informačních technologií Abstract:
[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.
Keywords:
approximate; matching; McCreight; online; preffix; string; substring; suffix; Suffix tree; Ukkonen; McCreight; odpovídající; online metoda; podřetězce; prefix; přibližný; sufix; Sufixový strom; Ukkonen; řetězec
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/55648