We apologize for a recent technical issue with our email system, which temporarily affected account activations. Accounts have now been activated. Authors may proceed with paper submissions. PhDFocusTM
CFP last date
20 November 2024
Call for Paper
December Edition
IJCA solicits high quality original research papers for the upcoming December edition of the journal. The last date of research paper submission is 20 November 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

Finding All Occurrences of a Pattern by a Genetic Algorithm Based Divide-and-Conquer Method

by Sagnik Banerjee, Tamal Chakrabarti, Devadatta Sinha
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 64 - Number 18
Year of Publication: 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 },
issue_date = { February 2013 },
volume = { 64 },
number = { 18 },
month = { February },
year = { 2013 },
issn = { 0975-8887 },
pages = { 48-52 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume64/number18/10737-5614/ },
doi = { 10.5120/10737-5614 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:16:49.478967+05:30
%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
%J International Journal of Computer Applications
%@ 0975-8887
%V 64
%N 18
%P 48-52
%D 2013
%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
  1. Banerjee Sagnik, Chakrabarti Tamal and Sinha Devadatta (2012), A Genetic Algorithm Based Pattern Matcher, International Journal of Scientific & Engineering Research, Volume 3, Issue 11
  2. Baeza-Yates. R. A. String Searching Algorithms Revisited. Lecture Notes in Computer Science, 382:75–96, 1989.
  3. Boyer R. and Moore J. S. A Fast String Searching Algorithm. Comm. of the ACM, 20:762–772, 1977.
  4. Colussi. L. Fastest Pattern Matching in Strings. Journal of Algorithms, 16:163–189, March 1994.
  5. Goldberg, D. E. (2011): Genetic Algorithms in Search, Optimization and Machine Learning, Pearson.
  6. Knuth D. , Morris J. and Pratt V. Fast Pattern Matching in Strings, SIAM Journal of Computer Science, pp323 – 350, 1977
  7. Mount David W. , Bioinformatics – Sequence and Genome Analysis, Cold Spring Harbor Laboratory Press, 2001.
  8. 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
  9. 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.
  10. 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.
  11. Smith-Keary. P. Molecular Genetics. Macmillan Education Ltd, London, 1991.
Index Terms

Computer Science
Information Sciences

Keywords

Divide and Conquer Pattern Matching Bioinformatics Genetic Algorithm

Powered by PhDFocusTM