Home   >   CSC-OpenAccess Library   >    Manuscript Information
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 
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].
D. E. Knuth, H. Morris, V. R. Pratt. Fast Pattern Matching in Strings, SIAM Journal of computing,vol. 6, pp. 323-350, 1977.
D.M. Sunday. A Very Fast Substring Search Algorithm, Journal of Communication of the ACM,vol. 33, pp. 132-142, 1990.
Hussain, M. Zubair, J. Ahmed, J. Zaffar. “Bidirectional Exact Pattern Matching Algorithm”,TCSET’2010, Feb. 2010, pp. 295.
J. H. Morris(Jr), V. R. Pratt. “A Linear Pattern Matching Algorithm”, 40th Technical Report,University of California, Berkeley, 1970.
M.Q. Zhang. “Computational prediction of eukaryotic protein-coding genes”, Nature Reviews Genetics, vol. 3, Sep. 2002, pp. 698-709.
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.
R.M. Karp, M.O. Rabin. Efficient Randomized Pattern Matching Algorithms, IBM J. Res. Dev,vol. 31, pp. 249-260, 1987.
R.S. Boyer, J.S. Moore. A Fast String Searching Algorithm, Communications of the ACM, vol. 20,pp.762-772, 1977.
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.
T. Berry, S. Ravindran. “A Fast String Matching Algorithm and Experimental Results”,Proceedings of the Stringology Club Workshop’99, 1999, pp. 16-26.
T.H. Cormen, C.E. Leiserson, R.L. Rivest. Introduction to Algorithms, MIT Press, First Edition,1990, pp. 853-885.
T.Raita.“Tuning the Boyer-Moore-Horspool string-searching algorithm”, Software – Practice Experience, 1992, pp. 879–884.
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.
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.
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


CREATE AUTHOR ACCOUNT
 
LAUNCH YOUR SPECIAL ISSUE
View all special issues >>
 
PUBLICATION VIDEOS