Comparative Study of String Matching Algorithms for DNA dataset

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[1].