Efficient String Matching Algorithm for Searching Large DNA and Binary Texts

Abdulrakeeb M. Al-Ssulami, Hassan Mathkour and Mohammed Amer Arafah
Additional contact information
Abdulrakeeb M. Al-Ssulami: Department of Computer Science, College of Computer & Information Sciences, King Saud University, Riyadh, Saudi Arabia
Hassan Mathkour: Department of Computer Science, College of Computer & Information Sciences, King Saud University, Riyadh, Saudi Arabia
Mohammed Amer Arafah: Department of Computer Engineering, College of Computer & Information Sciences, King Saud University, Riyadh, Saudi Arabia

International Journal on Semantic Web and Information Systems (IJSWIS), 2017, vol. 13, issue 4, 198-220

Abstract: The exact string matching is essential in application areas such as Bioinformatics and Intrusion Detection Systems. Speeding-up the string matching algorithm will therefore result in accelerating the searching process in DNA and binary data. Previously, there are two types of fast algorithms exist, bit-parallel based algorithms and hashing algorithms. The bit-parallel based are efficient when dealing with patterns of short lengths, less than 64, but slow on long patterns. On the other hand, hashing algorithms have optimal sublinear average case on large alphabets and long patterns, but the efficiency not so good on small alphabet such as DNA and binary texts. In this paper, the authors present hybrid algorithm to overcome the shortcomings of those previous algorithms. The proposed algorithm is based on q-gram hashing with guaranteeing the maximal shift in advance. Experimental results on random and complete human genome confirm that the proposed algorithm is efficient on various pattern lengths and small alphabet.

Date: 2017
References: Add references at CitEc
Citations:

Downloads: (external link)
https://services.igi-global.com/resolvedoi/resolve ... 18/IJSWIS.2017100110 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:igg:jswis0:v:13:y:2017:i:4:p:198-220

Access Statistics for this article

International Journal on Semantic Web and Information Systems (IJSWIS) is currently edited by Brij Gupta

More articles in International Journal on Semantic Web and Information Systems (IJSWIS) from IGI Global
Bibliographic data for series maintained by Journal Editor ().