|
|
Finding Approximate Palindromes in DNA Sequences
Remiáš, Richard ; Burgetová, Ivana (referee) ; Martínek, Tomáš (advisor)
This work discusses problematics of exact and approximate palindrome searching. In relation with exact palindrome searching, native algorithm and algorithm using suffix trees, which construction is also analyzed, is presented. Approximate palindrome search is implemented with application of dynamic programming principles. The search itself is dividded into three parts: palidnrome search, result filter and reconstruction of palindromes. Each part is described by an algorithm and implemented in a program, contained in attachment.
|
|
|
Suffix Trees Construction and Their Use in Bioinformatics
Hlaváček, Pavel ; Čermák, Martin (referee) ; Martínek, Tomáš (advisor)
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.
|
|
|
Suffix Trees Capabilities
Chlubna, Pavel ; Hynek, Jiří (referee) ; Burgetová, Ivana (advisor)
This thesis discusses structure of suffix trees, their implementation and problematics, we can solved with suffix trees. The thesis also focuses on construction of suffix trees, with usage of Ukkonen's algorithm. Apart of implementation of this structure this thesis deals with comparing other commonly used algorithms with suffix trees in term of time complexity. A result of this thesis is application with graphical interface, that shows usage of suffix trees in solving various problematics and shows comparison of this structure to other algorithms.
|
|
|
Suffix tree construction with minimized branching
Bašista, Peter ; Dvořák, Tomáš (advisor) ; Kadlec, Rudolf (referee)
Suffix tree is a data structure which enables the performing of fast search-like operations on the text. In order to be used efficiently, it must be created quickly. In this thesis, we focus on the new kind of suffix link simulation called "minimized branching", which aims to increase the speed of suffix tree construction by reducing the number of branching operations. Our main goal is to present a comparison of the currently used methods for the suffix tree construction and to point out some advantages and disadvantages of the individual approaches. We introduce, implement and practically evaluate multiple variations of the standard McCreight's and Ukkonen's algorithms, as well as Partition and Write Only Top Down (PWOTD) algorithm, originally developed for disk-based construction. Our main result is the integrated description and implementation of these algorithms, which are both well-suited to be further built upon. We also present a simple recommendations on when it is advisable to use a particular algorithm's variation and why.
|
|
|
Suffix Trees Capabilities
Chlubna, Pavel ; Hynek, Jiří (referee) ; Burgetová, Ivana (advisor)
This thesis discusses structure of suffix trees, their implementation and problematics, we can solved with suffix trees. The thesis also focuses on construction of suffix trees, with usage of Ukkonen's algorithm. Apart of implementation of this structure this thesis deals with comparing other commonly used algorithms with suffix trees in term of time complexity. A result of this thesis is application with graphical interface, that shows usage of suffix trees in solving various problematics and shows comparison of this structure to other algorithms.
|
|
|
Suffix Graphs and Lossless Data Compression
Senft, Martin ; Dvořák, Tomáš (advisor) ; Dvorský, Jiří (referee) ; Smyth, William F. (referee)
Title: Suffix Graphs and Lossless Data Compression Author: Martin Senft Department: Department of Software and Computer Science Education Supervisor of the doctoral thesis: doc. RNDr. Tomáš Dvorˇák, CSc., Depart- ment of Software and Computer Science Education Abstract: Suffix tree and its variants are widely studied data structures that enable an efficient solution to a number of string problems, but also serve for implementation of data compression algorithms. This work explores the opposite approach: design of compression methods, based entirely on prop- erties of suffix graphs. We describe a unified construction algorithm for suf- fix trie, suffix tree, DAWG and CDAWG, accompanied by analysis of implicit suffix link simulation that yields two practical alternatives. Since the com- pression applications require maintaining text in the sliding window, an in- depth discussionof slidingsuffixgraphsisneeded. Fillinggapsin previously published proofs, we verify that suffix tree is capable of perfect sliding in amortised constant time. On the other hand, we show that this is not the case with CDAWG, thus resolving a problem of Inenaga et al. Building on these investigations,we describea family of data compression methods,based on a description of suffix tree construction for the string to be compressed. While some of...
|
|
|
Suffix tree construction with minimized branching
Bašista, Peter ; Dvořák, Tomáš (advisor) ; Kadlec, Rudolf (referee)
Suffix tree is a data structure which enables the performing of fast search-like operations on the text. In order to be used efficiently, it must be created quickly. In this thesis, we focus on the new kind of suffix link simulation called "minimized branching", which aims to increase the speed of suffix tree construction by reducing the number of branching operations. Our main goal is to present a comparison of the currently used methods for the suffix tree construction and to point out some advantages and disadvantages of the individual approaches. We introduce, implement and practically evaluate multiple variations of the standard McCreight's and Ukkonen's algorithms, as well as Partition and Write Only Top Down (PWOTD) algorithm, originally developed for disk-based construction. Our main result is the integrated description and implementation of these algorithms, which are both well-suited to be further built upon. We also present a simple recommendations on when it is advisable to use a particular algorithm's variation and why.
|
|
|
Suffix Trees Construction and Their Use in Bioinformatics
Hlaváček, Pavel ; Čermák, Martin (referee) ; Martínek, Tomáš (advisor)
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.
|
|
|
Finding Approximate Palindromes in DNA Sequences
Remiáš, Richard ; Burgetová, Ivana (referee) ; Martínek, Tomáš (advisor)
This work discusses problematics of exact and approximate palindrome searching. In relation with exact palindrome searching, native algorithm and algorithm using suffix trees, which construction is also analyzed, is presented. Approximate palindrome search is implemented with application of dynamic programming principles. The search itself is dividded into three parts: palidnrome search, result filter and reconstruction of palindromes. Each part is described by an algorithm and implemented in a program, contained in attachment.
|
guest ::
