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.
Original language  English 

Qualification  Doctor's degree 
Awarding Institution 

Supervisors/Advisors 

Publisher  
Print ISBNs  9789526077574 
Electronic ISBNs  9789526077581 
Publication status  Published  2017 
MoE publication type  G4 Doctoral dissertation (monograph) 
Keywords
 jumbled pattern matching
 algorithms
Fingerprint Dive into the research topics of 'Improved Online Algorithms for Jumbled Matching'. Together they form a unique fingerprint.
Cite this
Ghuman, S. S. (2017). Improved Online Algorithms for Jumbled Matching. Aalto University.