Improved Online Algorithms for Jumbled Matching

dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.advisorTarhio, Jorma, Prof., Aalto University, Department of Computer Science, Finland
dc.contributor.authorGhuman, Sukhpal Singh
dc.contributor.departmentTietotekniikan laitosfi
dc.contributor.departmentDepartment of Computer Scienceen
dc.contributor.schoolPerustieteiden korkeakoulufi
dc.contributor.schoolSchool of Scienceen
dc.contributor.supervisorTarhio, Jorma, Prof., Aalto University, Department of Computer Science, Finland
dc.date.accessioned2018-01-17T10:03:05Z
dc.date.available2018-01-17T10:03:05Z
dc.date.defence2018-01-15
dc.date.issued2017
dc.description.abstractIn 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.en
dc.format.extent118
dc.identifier.isbn978-952-60-7758-1 (electronic)
dc.identifier.isbn978-952-60-7757-4 (printed)
dc.identifier.issn1799-4942 (electronic)
dc.identifier.issn1799-4934 (printed)
dc.identifier.issn1799-4934 (ISSN-L)
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/29631
dc.identifier.urnURN:ISBN:978-952-60-7758-1
dc.language.isoenen
dc.opnKülekci, M. Oğuzhan, Asst. Prof., Istanbul Technical University, Turkey
dc.publisherAalto Universityen
dc.publisherAalto-yliopistofi
dc.relation.ispartofseriesAalto University publication series DOCTORAL DISSERTATIONSen
dc.relation.ispartofseries242/2017
dc.revWatson, Bruce, Prof., Stellenbosch University, South Africa
dc.revFredriksson, Kimmo, Adj. Prof., University of Eastern Finland, Finland
dc.subject.keywordjumbled pattern matchingen
dc.subject.keywordalgorithmsen
dc.subject.otherComputer scienceen
dc.titleImproved Online Algorithms for Jumbled Matchingen
dc.typeG4 Monografiaväitöskirjafi
dc.type.dcmitypetexten
dc.type.ontasotDoctoral dissertation (monograph)en
dc.type.ontasotVäitöskirja (monografia)fi
local.aalto.archiveyes
local.aalto.formfolder2018_01_16_klo_16_48
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
isbn9789526077581.pdf
Size:
623.22 KB
Format:
Adobe Portable Document Format
Description: