|
|
Approximate String Matching in Preprocessed Documents
Toth, Róbert ; Košař, Vlastimil (referee) ; Kaštil, Jan (advisor)
This thesis deals with the problem of approximate string matching, also called string matching allowing errors. The thesis targets the area of offline algorithms, which allows very fast pattern matching thanks to index created during initial text preprocessing phase. Initially, we will define the problem itself and demonstrate variety of its applications, followed by short survey of different approaches to cope with this problem. Several existing algorithms based on suffix trees will be explained in detail and new hybrid algorithm will be proposed. Algorithms wil be implemented in C programming language and thoroughly compared in series of experiments with focus on newly presented algorithm.
|
|
|
Aproximate String Matching
Toth, Róbert ; Košař, Vlastimil (referee) ; Kaštil, Jan (advisor)
This thesis deals with the problem of approximate string matching, ie. string matching allowing errors. Initially, we will define the problem itself and demonstrate variety of it's applications, followed by short survey of different approaches to cope with this problem. The remaining part of the work is focused on algorithms based on the use of deterministic finite automatons. Main algorithms in this area will be presented. Those will be implemented in Python programming language and thoroughly compared in series of experiments.
|
|
|
Acceleration of Algorithms for Approximate String Matching Using FPGA
Beck, Patrik ; Kořenek, Jan (referee) ; Martínek, Tomáš (advisor)
This work describes implementation of hardware device for approximate string matching of biological sequences. Matchnig is performed using Smith-Waterman and Needleman-Wunsch algorithms. Device can be used as an accelerator for bioinformatics algorithms on higher level. This accelerator can be used for human genome analysis, matching proteins against a database, revealing inheritance information. Depending on task character, the acceleration speed up achieves several orders of magniture in comparison with conventional computers.
|
|
|
Acceleration of Algorithms for Approximate String Matching
Voženílek, Jan ; Kořenek, Jan (referee) ; Martínek, Tomáš (advisor)
The objective of this bachelor's thesis is to design and implement architecture for FPGA chips that accelerates matching of two strings and scoring them for similarity. Used processes come from bioinformatics algorithms, especially Needleman-Wunsch and Smith-Waterman. Due to general design and generic implementation in VHDL the unit is able to compare any sequences of characters, which is a task widely used in many branches of informatics from database searches (where approximate matching allows discovery of spelling errors) to spam detection. Depending on task specification the acceleration speed up against common software solution can reach orders of hundreds or even thousands.
|
|
|
Acceleration of Algorithms for Approximate String Matching Using FPGA
Beck, Patrik ; Kořenek, Jan (referee) ; Martínek, Tomáš (advisor)
This work describes implementation of hardware device for approximate string matching of biological sequences. Matchnig is performed using Smith-Waterman and Needleman-Wunsch algorithms. Device can be used as an accelerator for bioinformatics algorithms on higher level. This accelerator can be used for human genome analysis, matching proteins against a database, revealing inheritance information. Depending on task character, the acceleration speed up achieves several orders of magniture in comparison with conventional computers.
|
|
|
Aproximate String Matching
Toth, Róbert ; Košař, Vlastimil (referee) ; Kaštil, Jan (advisor)
This thesis deals with the problem of approximate string matching, ie. string matching allowing errors. Initially, we will define the problem itself and demonstrate variety of it's applications, followed by short survey of different approaches to cope with this problem. The remaining part of the work is focused on algorithms based on the use of deterministic finite automatons. Main algorithms in this area will be presented. Those will be implemented in Python programming language and thoroughly compared in series of experiments.
|
|
|
Approximate String Matching in Preprocessed Documents
Toth, Róbert ; Košař, Vlastimil (referee) ; Kaštil, Jan (advisor)
This thesis deals with the problem of approximate string matching, also called string matching allowing errors. The thesis targets the area of offline algorithms, which allows very fast pattern matching thanks to index created during initial text preprocessing phase. Initially, we will define the problem itself and demonstrate variety of its applications, followed by short survey of different approaches to cope with this problem. Several existing algorithms based on suffix trees will be explained in detail and new hybrid algorithm will be proposed. Algorithms wil be implemented in C programming language and thoroughly compared in series of experiments with focus on newly presented algorithm.
|
|
|
Acceleration of Algorithms for Approximate String Matching
Voženílek, Jan ; Kořenek, Jan (referee) ; Martínek, Tomáš (advisor)
The objective of this bachelor's thesis is to design and implement architecture for FPGA chips that accelerates matching of two strings and scoring them for similarity. Used processes come from bioinformatics algorithms, especially Needleman-Wunsch and Smith-Waterman. Due to general design and generic implementation in VHDL the unit is able to compare any sequences of characters, which is a task widely used in many branches of informatics from database searches (where approximate matching allows discovery of spelling errors) to spam detection. Depending on task specification the acceleration speed up against common software solution can reach orders of hundreds or even thousands.
|
guest ::
