Home   >   CSC-OpenAccess Library   >    Manuscript Information
Full Text Available

(182.62KB)
This is an Open Access publication published under CSC-OpenAccess Policy.
Publications from CSC-OpenAccess Library are being accessed from over 74 countries worldwide.
An Application of Pattern matching for Motif Identification
Kishore Kumar Senapati, Dibya Ranjan Das Adhikari, Gadadhar Sahoo
Pages - 135 - 143     |    Revised - 15-09-2012     |    Published - 24-10-2012
Volume - 6   Issue - 5    |    Publication Date - October 2012  Table of Contents
MORE INFORMATION
KEYWORDS
Motif Finding, Pattern Matching, Preprocessing, Gene finding
ABSTRACT
Pattern matching is one of the central and most widely studied problem in theoretical computer science. Solutions to the problem play an important role in many areas of science and information processing. Its performance has great impact on many applications including database query, text processing and DNA sequence analysis. In general Pattern matching algorithms are based on the shift value, the direction of the sliding window and the order in which comparisons are made. The performance of the algorithms can be enhanced to a great extent by a larger shift value and less number of comparison to get the shift value. In this paper we proposed an algorithm, for finding motif in DNA sequence. The algorithm is based on preprocessing of the pattern string(motif) by considering four consecutive nucleotides of the DNA that immediately follow the aligned pattern window in an event of mismatch between pattern(motif) and DNA sequence .Theoretically, we found the proposed algorithms work efficiently for motif identification.
CITED BY (1)  
1 Ahmad, M. K. (2014). An Enhanced Boyer-Moore Algorithm (Doctoral dissertation, Middle East University).
1 Google Scholar 
2 CiteSeerX 
3 refSeek 
4 Scribd 
5 SlideShare 
6 PdfSR 
1 T.H. Cormen, C.E. Leiserson, R.L. Rivest. Introduction to Algorithms, MIT Press, First Edition,1990, pp. 853-885.
2 C. Charras, T. Lecroq(1997). Handbook of Exact String Matching Algorithms. [online]. Available:http://www-igm.univ-mlv.fr/~lecroq/string/string.pdf [Oct 08, 2012].
3 R.S. Boyer, J.S. Moore. A Fast String Searching Algorithm, Communications of the ACM, vol. 20,pp.762-772, 1977.
4 D.M. Sunday. A Very Fast Substring Search Algorithm, Journal of Communication of the ACM,vol. 33, pp. 132-142, 1990.
5 R.M. Karp, M.O. Rabin. Efficient Randomized Pattern Matching Algorithms, IBM J. Res. Dev,vol. 31, pp. 249-260, 1987.
6 T.Raita.“Tuning the Boyer-Moore-Horspool string-searching algorithm”, Software – Practice Experience, 1992, pp. 879–884.
7 T. Berry, S. Ravindran. “A Fast String Matching Algorithm and Experimental Results”,Proceedings of the Stringology Club Workshop’99, 1999, pp. 16-26.
8 R. Thathoo,A. Virmani, S. Lakshmi, N. Balakrishnan, K. Sekar. TVSBS: A Fast Exact Pattern Matching Algorithm for Biological Sequences, Current Science, vol. 91, pp. 47-53, Jul. 2006.
9 D. E. Knuth, H. Morris, V. R. Pratt. Fast Pattern Matching in Strings, SIAM Journal of computing,vol. 6, pp. 323-350, 1977.
10 J. H. Morris(Jr), V. R. Pratt. “A Linear Pattern Matching Algorithm”, 40th Technical Report,University of California, Berkeley, 1970.
11 Y.Huang, L. Ping, X. Pan, G. Cai. “A Fast Exact Pattern Matching Algorithm for Biological Sequences”, International Conference on Biomedical Engineering and Informatics, IEEE computer Society, Feb. 2008, pp. 8-12.
12 V. Radhakrishna, B. Phaneendra, V.S. Kumar. “A Two Way Pattern Matching Algorithm Using Sliding Patterns”, 3rd International Conforence on Advanced Computer Theory and Engineering (ICACTE), 2010, vol. 2, pp. 666-670.
13 Hussain, M. Zubair, J. Ahmed, J. Zaffar. “Bidirectional Exact Pattern Matching Algorithm”,TCSET’2010, Feb. 2010, pp. 295.
14 S. S.Sheik,S. K. Aggarwal, A. Poddar, N. Balakrishnan, K. Sekar.A FAST Pattern Matching Algorithm, Journal of Chemical Information and Computer Sciences, vol.44, pp. 1251–1256,2004.
15 M.Q. Zhang. “Computational prediction of eukaryotic protein-coding genes”, Nature Reviews Genetics, vol. 3, Sep. 2002, pp. 698-709.
Mr. Kishore Kumar Senapati
BIRLA INSTITUTE OF TECHNOLOGY - India
kksenapati@bitmesra.ac.in
Mr. Dibya Ranjan Das Adhikari
BIRLA INSTITUTE OF TECHNOLOGY - India
Dr. Gadadhar Sahoo
BIRLA INSTITUTE OF TECHNOLOGY - India