Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 30843
An Index based Forward Backward Multiple Pattern Matching Algorithm

Authors: Raju Bhukya, DVLN Somayajulu


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: index, comparisons, DNA sequence

Digital Object Identifier (DOI):

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2062


[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.