|
|
Whole genome alignment using suffix trees
Klouba, Lukáš ; Sedlář, Karel (referee) ; Maděránková, Denisa (advisor)
The aim of this thesis is to create an algorithm that allows the alignment of the genome of two organisms by means of suffix structures and to implement it into the programming language environment R. The thesis deals with the description of the construction of the suffix structures and the methods of whole genome alignment. The result of the thesis is a functional algorithm for whole genome alignment by means of suffix structures implemented in the software environment R and its comparison with similar programs for the whole genome alignment.
|
|
|
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.
|
|
|
Approximate Palindrome Detection in DNA Sequences
Divila, Jaroslav ; Lexa, Matej (referee) ; Martínek, Tomáš (advisor)
This work deals with conception and implemetation of tools for finding approximate palindromes in DNA sequences. The work focuses on the description of DNA structure, and on the function of palindromes in DNA sequences, and on the description of methods for finding approximate palindromes. Main part of thesis is focused on conclusion and description of implementation approximate palidromes finding tool.
|
|
|
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...
|
|
|
Whole genome alignment using suffix trees
Klouba, Lukáš ; Sedlář, Karel (referee) ; Maděránková, Denisa (advisor)
The aim of this thesis is to create an algorithm that allows the alignment of the genome of two organisms by means of suffix structures and to implement it into the programming language environment R. The thesis deals with the description of the construction of the suffix structures and the methods of whole genome alignment. The result of the thesis is a functional algorithm for whole genome alignment by means of suffix structures implemented in the software environment R and its comparison with similar programs for the whole genome alignment.
|
|
|
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.
|
guest ::
