Research Article
Finding All Occurrences of a Pattern by a Genetic Algorithm Based Divide-and-Conquer Method
|
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
| Volume 64 - Issue 18 |
| Published: February 2013 |
| Authors: Sagnik Banerjee, Tamal Chakrabarti, Devadatta Sinha |
10.5120/10737-5614
|
Sagnik Banerjee, Tamal Chakrabarti, Devadatta Sinha . Finding All Occurrences of a Pattern by a Genetic Algorithm Based Divide-and-Conquer Method. International Journal of Computer Applications. 64, 18 (February 2013), 48-52. DOI=10.5120/10737-5614
@article{ 10.5120/10737-5614,
author = { Sagnik Banerjee,Tamal Chakrabarti,Devadatta Sinha },
title = { Finding All Occurrences of a Pattern by a Genetic Algorithm Based Divide-and-Conquer Method },
journal = { International Journal of Computer Applications },
year = { 2013 },
volume = { 64 },
number = { 18 },
pages = { 48-52 },
doi = { 10.5120/10737-5614 },
publisher = { Foundation of Computer Science (FCS), NY, USA }
}
%0 Journal Article
%D 2013
%A Sagnik Banerjee
%A Tamal Chakrabarti
%A Devadatta Sinha
%T Finding All Occurrences of a Pattern by a Genetic Algorithm Based Divide-and-Conquer Method%T
%J International Journal of Computer Applications
%V 64
%N 18
%P 48-52
%R 10.5120/10737-5614
%I Foundation of Computer Science (FCS), NY, USA
Abstract
The method of finding a sequence of characters, called the pattern, in another much longer sequence of characters, called the text, is known as pattern matching. Several pattern-matching algorithms exist, that locate all the positions where a pattern occurs in a text. In this paper we have presented an algorithm which implements a divide and conquer technique, which divides the text in smaller independent sub-texts and then looks for the existence of the pattern in each such sub-text. The said divide and conquer method thus eventually finds all the occurrences of the pattern in the given text. The points of division have been chosen using a genetic algorithm.
References
- Banerjee Sagnik, Chakrabarti Tamal and Sinha Devadatta (2012), A Genetic Algorithm Based Pattern Matcher, International Journal of Scientific & Engineering Research, Volume 3, Issue 11
- Baeza-Yates. R. A. String Searching Algorithms Revisited. Lecture Notes in Computer Science, 382:75–96, 1989.
- Boyer R. and Moore J. S. A Fast String Searching Algorithm. Comm. of the ACM, 20:762–772, 1977.
- Colussi. L. Fastest Pattern Matching in Strings. Journal of Algorithms, 16:163–189, March 1994.
- Goldberg, D. E. (2011): Genetic Algorithms in Search, Optimization and Machine Learning, Pearson.
- Knuth D. , Morris J. and Pratt V. Fast Pattern Matching in Strings, SIAM Journal of Computer Science, pp323 – 350, 1977
- Mount David W. , Bioinformatics – Sequence and Genome Analysis, Cold Spring Harbor Laboratory Press, 2001.
- Navarro G. and M. Raffinot. Fast and Simple Character Classes and Bounded Gaps Pattern Matching, With Application to Protein Searching. In Annual Conference on Research in Computational Molecular Biology, Montreal, Canada, 2001
- Rajesh S. , Prathima S. , Reddy L. S. S. , Unusual Pattern Detection in DNA Database Using KMP Algorithm, International Journal of Computer Applications (0975 - 8887)Volume 1 – No. 22, 2010.
- Simone Faro and Thierry Lecroq. An Efficient Matching Algorithm for Encoded DNA Sequences and Binary Strings. Lecture Notes in Computer Science, 2009, Volume 5577/2009, 106-115.
- Smith-Keary. P. Molecular Genetics. Macmillan Education Ltd, London, 1991.
Index Terms
Keywords