Defence of dissertation in the field of computer science, Sukhpal Ghuman, M.Eng.
Improving Algorithms for Finding Scrambled Patterns
Sukhpal Ghuman, M.Eng, will defend the dissertation "Improved Online Algorithms for Jumbled Matching" at the Aalto University School of Science. This dissertation focuses on the improvement of online algorithms for exact and approximate jumbled matching using the features of single microprocessors such as parallel processing.
Searching of text patterns is a widely studied problem in Computer Science. This dissertation considers a variation called jumbled matching where scrambled occurrences are accepted besides exact occurrences. For example, there is a scrambled occurrence of the pattern “prime” in the text “this is an experiment”. The problem of jumbled matching has many applications in Bioinformatics.
Besides standard jumbled matching we worked on an approximate variation where each occurrence is allowed to contain at most k wrong or superfluous characters. We present online algorithms to both types of jumbled matching that utilize parallel processing features of single microprocessors (bit-parallelism and SIMD). We show by practical experiments that our algorithms are faster than previous solutions in most cases.
Dissertation Release (pdf)
Opponent: Associate Professor M. Oğuzhan Külekci, Istanbul Technical University, Turkey
Custos: Professor Jorma Tarhio, Aalto University School of Science, Department of Computer Science