Improved Online Algorithms for Jumbled Matching

Research output: ThesisDoctoral ThesisMonograph

Researchers

  • Sukhpal Singh Ghuman

Research units

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.

Details

Translated title of the contributionImproved Online Algorithms for Jumbled Matching
Original languageEnglish
QualificationDoctor's degree
Awarding Institution
Supervisors/Advisors
Publisher
  • Aalto University
Print ISBNs978-952-60-7757-4
Electronic ISBNs978-952-60-7758-1
Publication statusPublished - 2017
MoE publication typeG4 Doctoral dissertation (monograph)

    Research areas

  • jumbled pattern matching, algorithms

ID: 17676593