An Index based Forward Backward Multiple Pattern Matching Algorithm

Authors: Raju Bhukya, DVLN Somayajulu

Abstract:

Pattern matching is one of the fundamental applications in molecular biology. Searching DNA related data is a common activity for molecular biologists. In this paper we explore the applicability of a new pattern matching technique called Index based Forward Backward Multiple Pattern Matching algorithm(IFBMPM), for DNA Sequences. Our approach avoids unnecessary comparisons in the DNA Sequence due to this; the number of comparisons of the proposed algorithm is very less compared to other existing popular methods. The number of comparisons rapidly decreases and execution time decreases accordingly and shows better performance.

Keywords: Comparisons, DNA Sequence, Index.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1083901

References:

[1] Boyer R. S., and J. S. Moore, "A fast string searching algorithm, " Communications of the ACM 20 (October 1977), pp. 762 772.
[2] Knuth D., Morris.J Pratt.V Fast pattern matching in strings, SIAM journal on computing.
[3] Kurtz. S, Approximate string searching under weighted edit distance. In proceedings of the 3rd south American workshop on string processing. (WSP 96). Carleton Univ Press, 1996 156-170.
[4] Needleman,S.B Wunsch, C.D(1970). A general method applicable to the search for similarities in the amino acid sequence of two proteins. J.Mol.Biol.48,443-453.
[5] Ukkonen,E., Finding approximate patterns in strings J.Algor. 6, 1985, 132-137
[6] Wu S., and U. Manber, "Agrep - A Fast Approximate Pattern- Matching Tool" Usenix Winter 1992 Technical Conference, San Francisco (January 1992), pp. 153 162.
[7] WU.S.,Manber U., and Myers,E .1996, A sub-quadratic algorithm for approximate limited expression matching. Algorithmica 15,1,50-67, Computer Science Dept, University of Arizona,1992.
[8] (MSMPMA) Ziad A.A Alqadi, Musbah Aqel & Ibrahiem M.M.EI Emary, Multiple Skip Multiple Pattern Matching algorithms. IAENG International Journal of Computer Science 34:2.