Improved Online Algorithms for Jumbled Matching

Sukhpal Singh Ghuman

Research output: ThesisDoctoral ThesisMonograph

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 languageEnglish
QualificationDoctor's degree
Awarding Institution
  • Aalto University
Supervisors/Advisors
  • Tarhio, Jorma, Supervisor
  • Tarhio, Jorma, Advisor
Publisher
Print ISBNs978-952-60-7757-4
Electronic ISBNs978-952-60-7758-1
Publication statusPublished - 2017
MoE publication typeG4 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.