Improved Online Algorithms for Jumbled Matching

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.advisor Tarhio, Jorma, Prof., Aalto University, Department of Computer Science, Finland Ghuman, Sukhpal Singh 2018-01-17T10:03:05Z 2018-01-17T10:03:05Z 2017
dc.identifier.isbn 978-952-60-7758-1 (electronic)
dc.identifier.isbn 978-952-60-7757-4 (printed)
dc.identifier.issn 1799-4942 (electronic)
dc.identifier.issn 1799-4934 (printed)
dc.identifier.issn 1799-4934 (ISSN-L)
dc.description.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. en
dc.format.extent 118
dc.language.iso en en
dc.publisher Aalto University en
dc.publisher Aalto-yliopisto fi
dc.relation.ispartofseries Aalto University publication series DOCTORAL DISSERTATIONS en
dc.relation.ispartofseries 242/2017
dc.subject.other Computer science en
dc.title Improved Online Algorithms for Jumbled Matching en
dc.type G4 Monografiaväitöskirja fi Perustieteiden korkeakoulu fi School of Science en
dc.contributor.department Tietotekniikan laitos fi
dc.contributor.department Department of Computer Science en
dc.subject.keyword jumbled pattern matching en
dc.subject.keyword algorithms en
dc.identifier.urn URN:ISBN:978-952-60-7758-1
dc.type.dcmitype text en
dc.type.ontasot Doctoral dissertation (monograph) en
dc.type.ontasot Väitöskirja (monografia) fi
dc.contributor.supervisor Tarhio, Jorma, Prof., Aalto University, Department of Computer Science, Finland
dc.opn Külekci, M. Oğuzhan, Asst. Prof., Istanbul Technical University, Turkey
dc.rev Watson, Bruce, Prof., Stellenbosch University, South Africa
dc.rev Fredriksson, Kimmo, Adj. Prof., University of Eastern Finland, Finland 2018-01-15

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search archive

Advanced Search

article-iconSubmit a publication


My Account