Open Access   Article Go Back

Comparative Study of String Matching Algorithms for DNA dataset

Pooja Manisha Rahate1 , M. B. Chandak2

  1. Dept. of Computer Science and Tech., Shri Ramdeobaba College of Engineering & Management, Nagpur, Maharashtra, India.
  2. Dept. of Computer Science and Tech., Shri Ramdeobaba College of Engineering & Management, Nagpur, Maharashtra, India.
  3. Dept. of Computer Science and Tech., Shri Ramdeobaba College of Engineering & Management, Nagpur, Maharashtra, India.

Section:Research Paper, Product Type: Journal Paper
Volume-6 , Issue-5 , Page no. 1067-1074, May-2018

CrossRef-DOI:   https://doi.org/10.26438/ijcse/v6i5.10671074

Online published on May 31, 2018

Copyright © Pooja Manisha Rahate, M. B. Chandak . This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

View this paper at   Google Scholar | DPI Digital Library

XML View
PDF Download

How to Cite this Paper

  • IEEE Citation
  • MLA Citation
  • APA Citation
  • BibTex Citation
  • RIS Citation

IEEE Style Citation: Pooja Manisha Rahate, M. B. Chandak, “Comparative Study of String Matching Algorithms for DNA dataset,” International Journal of Computer Sciences and Engineering, Vol.6, Issue.5, pp.1067-1074, 2018.

MLA Style Citation: Pooja Manisha Rahate, M. B. Chandak "Comparative Study of String Matching Algorithms for DNA dataset." International Journal of Computer Sciences and Engineering 6.5 (2018): 1067-1074.

APA Style Citation: Pooja Manisha Rahate, M. B. Chandak, (2018). Comparative Study of String Matching Algorithms for DNA dataset. International Journal of Computer Sciences and Engineering, 6(5), 1067-1074.

BibTex Style Citation:
@article{Rahate_2018,
author = {Pooja Manisha Rahate, M. B. Chandak},
title = {Comparative Study of String Matching Algorithms for DNA dataset},
journal = {International Journal of Computer Sciences and Engineering},
issue_date = {5 2018},
volume = {6},
Issue = {5},
month = {5},
year = {2018},
issn = {2347-2693},
pages = {1067-1074},
url = {https://www.ijcseonline.org/full_paper_view.php?paper_id=2110},
doi = {https://doi.org/10.26438/ijcse/v6i5.10671074}
publisher = {IJCSE, Indore, INDIA},
}

RIS Style Citation:
TY - JOUR
DO = {https://doi.org/10.26438/ijcse/v6i5.10671074}
UR - https://www.ijcseonline.org/full_paper_view.php?paper_id=2110
TI - Comparative Study of String Matching Algorithms for DNA dataset
T2 - International Journal of Computer Sciences and Engineering
AU - Pooja Manisha Rahate, M. B. Chandak
PY - 2018
DA - 2018/05/31
PB - IJCSE, Indore, INDIA
SP - 1067-1074
IS - 5
VL - 6
SN - 2347-2693
ER -

VIEWS PDF XML
720 411 downloads 268 downloads
  
  
           

Abstract

String matching algorithms are widely used in computer science fields for information retrieval, intrusion detection, music retrieval, database queries, language syntax checker, bioinformatics, DNA sequence matching and etc. The most common and well-known use of string matching algorithms is for bioinformatics. In bioinformatics the DNA sequences of the normal human being and matched with the DNA sequence of a person having viruses or any kind disease. The pattern of any disease or virus is matched with the normal DNA genome sequence. If the pattern is found in the sequence which is in the form of string it is considered that the human being or patient is having the tested disease. Thus the pattern is matched with the large amount of DNA sequence which is sometimes very complex and not easy to retrieve. Thus to get the result or matched pattern in the less time with more accuracy the algorithms such as Knuth-Morris-Pratt(KMP), Boyer-Moore, Brute Force, Rabin-Karp and other algorithms are used. This paper presents five string matching algorithms from which four are exact matching algorithms and one is approximate string matching algorithm (Edit Distance). The above listed algorithms complexity will be compared using the DNA dataset to find the appropriate algorithm with high quality time and accuracy.

Key-Words / Index Term

String Matching Algorithm, DNA sequence

References

[1] NYO ME TUN, THIN MYA MYA SWE, “Comparison of Three Pattern Matching Algorithms using DNA Sequences”, IJSETR, Vol.3, Issue.35, pp.6916-6920, 2014.
[2] https://en.wikipedia.org/wiki/DNA
[3] Robert Sedgewick, Kevin Wayne, “Algorithms”, Fourth Edition, Addison-Wesley,Pearson Edition, India, pp. 760-776, 2011.
[4] Thomas Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford Stein, “Introduction to Algorithms”, McGraw-Hill Publication, India, pp.909-926, 2001.
[5] Raju Bhukya, DVLN Somayajulu, “Exact Multiple Pattern Matching Algorithm using DNA Sequence and Pattern Pair”, International Journal of Computer Applications, Number 8,Article 6, pp.32-38, 2011.
[6] Petteri Jokinen, Jorma Tarhio and Esko Ukkonen, “A Comparison of Approximate String Matching Algorithms”, Software-Practice and Experience, Vol.1(1), pp.1-4, 1988.
[7] http://ccg.vitalit.ch/cgibin/htpselex/show?htpselex&tf=NF1_1&clone
[8] https://archive.ics.uci.edu/ml/machine-learning-databases/molecular-biology/promoter-gene-sequences/promoters.data