Improved Online Algorithms for Jumbled Matching

Loading...
Thumbnail Image
Journal Title
Journal ISSN
Volume Title
School of Science | Doctoral thesis (monograph) | Defence date: 2018-01-15
Date
2017
Major/Subject
Mcode
Degree programme
Language
en
Pages
118
Series
Aalto University publication series DOCTORAL DISSERTATIONS, 242/2017
Abstract
In Computer Science, the problem of finding the occurrences of a given string is a common task. There are many different variations of the problem. We consider the problem of jumbled pattern matching (JPM) (also known as Abelian pattern matching or permutation matching) where the objective is to find all permuted occurrences of a pattern in a text. Jumbled pattern matching has numerous applications in the field of bioinformatics. For instance, jumbled matching can be used to find those genes that are closely related to one another. Besides exact jumbled matching we study approximate jumbled matching where each occurrence is allowed to contain at most k wrong or superfluous characters. We present online algorithms applying bitparallelism to both types of jumbled matching. Two of our algorithms are filtration methods applying SIMD (Single Instruction Multiple Data) computation. Furthermore, we have developed a bitparallel algorithm for episode matching. This algorithm finds the maximal parallel episodes of a given sequence. Most of the other new algorithms are variations of earlier methods. We show by practical experiments that our algorithms are competitive with previous solutions.
Description
Supervising professor
Tarhio, Jorma, Prof., Aalto University, Department of Computer Science, Finland
Thesis advisor
Tarhio, Jorma, Prof., Aalto University, Department of Computer Science, Finland
Keywords
jumbled pattern matching, algorithms
Other note
Citation