Abstract

In this study, a new algorithm for the traditional pattern matching problem has been proposed. This algorithm is a modified version of KMP algorithm and using bitwise XOR operation to process two characters (or bytes) in parallel, to speed up the pattern matching process. An additional loop to avoid the undesirable comparison(s) also been introduced and let the algorithm to initiate, and continue only the essential comparisons from the required location. As the new algorithm uses the principle of Finite automata which is used by KMP algorithm and Bitwise XOR operation to speed up the character match, it shows some reasonable performance improvement. Also this new algorithm is easy to implement as it doesn't require any additional/complex data structure(s) and suitable for DNA sequence search.

References

• Baeza-Yates, R. A. and Gonnet, G. H. 1992. A new approach to text searching. Communications of the ACM 35, 10, 74–82.
• Bálint Dömölki, An algorithm for syntactical analysis, Computational Linguistics 3, Hungarian Academy of Science pp. 29–46, 1964.
• Knuth, Donald; Morris, James H. , jr; Pratt, Vaughan (1977). "Fast pattern matching in strings". SIAM Journal on Computing 6 (2): 323–350.
• Boyer, Robert S. ; Moore, J Strother (October 1977). "A Fast String Searching Algorithm. ". Communications of the ACM (New York, NY, USA: Association for Computing Machinery) 20 (10): 762–772.
• Karp, R. M. , Rabin, M. O. , 1987, Efficient randomized pattern-matching algorithms, IBM Journal on Research Development 31(2):249-260.
• A. Blumer, J. Blumer, A. Ehrenfeucht, D. Haussler, and R. McConnel: Linear size finite automata for the set of all subwords of a word: an outline of results. Bull. Eur. Assoc. Theor. Comput. Sci. , 21 1983, pp. 12–20.
• M. Crochemore: Optimal factor tranducers, in Combinatorial Algorithms on Words, A. Apostolico and Z. Galil, eds. , vol. 12 of NATO Advanced Science Institutes, Series F, Springer-Verlag, Berlin, 1985, pp. 31–44.
• A. Blumer, J. Blumer, A. Ehrenfeucht, D. Haussler, M. T. Chen, and J. Seiferas: The smallest automaton recognizing the subwords of a text. Theor. Comput. Sci. , 40(1) 1985, pp. 31–55.
• C. Allauzen, M. Crochemore, and M. Raffinot: Factor oracle: a new structure for pattern matching, in SOFSEM'99, J. Pavelka, G. Tel, and M. Bartosek, eds. , LNCS 1725, Milovy, Czech Republic, 1999, Springer-Verlag, Berlin, pp. 291–306.
• Galil, Z. , and Giancarlo, R. Improved string matching with k mismatches. SIGACT News 17 (1986), 52-54.
• Landau, G. M. , and Vishkin, U. Fast string matching with k differences. J. Comput. System Sci. 37 (1988), 63-78.
• Landau, G. M. , and Vishkin, U. Fast parallel and serial approximate string matching. Journal of Algorithms 10 (1989).
• J. Holub and B. Durian. Fast variants of bit parallel approach to suffix automata. Unpublished Lecture, University of Haifa, April 2005.
• G. Navarro and M. Raffinot. Fast and flexible string matching by combining bit-parallelism and suffix automata. ACM Journal of Experimental Algorithms, 5(4):1-36, 2000.
• H. Peltola and J. Tarhio. Alternative algorithms for bit-parallel string matching. In LNCS 2857, Proceedings of SPIRE'2003, pages 80-94, 2003.
• G. Navarro and M. Raffinot. A bit-parallel approach to suffix automata: Fast extended string matching. In CPM, volume 1448 of LNCS, pages 14–33. Springer-Verlag, 1998.
• B. Commentz-Walter. A string matching algorithm fast on the average. In ICALP, volume 71 of LNCS, pages 118–132, 1979.
• Simone Faro, Thierry Lecroq: An Efficient Matching Algorithm for Encoded DNA Sequences and Binary Strings. CPM 2009: 106-115.
• J. W. Kim, E. Kim, and K. Park. Fast matching method for DNA sequences. In Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, volume 4614 of LNCS, pages 271–281, 2007.
• D. M. Sunday. A very fast substring search algorithm. Commun. ACM, 33(8):132–142, 1990.
• Human DNA Sequences downloaded from, ftp://ftp. ncbi. nlm. nih. gov