A Fast Hybrid Algorithm Approach for the Exact String Matching Problem Via Berry Ravindran and Alpha Skip Search Algorithms

Abstract

Problem statement: String matching algorithm had been an essential means for searching biological sequence database. With the constant expansion in scientific data such as DNA and Protein; the development of enhanced algorithms have even become more critical as the major concern had always been how to raise the performances of these search algorithms to meet challenges of scientific information. Approach: Therefore a new hybrid algorithm comprising Berry Ravindran (BR) and Alpha Skip Search (ASS) is presented. The concept is based on BR shift function and combines with ASS to ensure improved performance. Results: The results obtained in percentages from the proposed hybrid algorithm displayed superior results in terms of number of attempts and number of character comparisons than the original algorithms when various types of data namely DNA, Protein and English text are applied to appraise the hybrid performances. The enhancement of the proposed hybrid algorithm performs better at 71%, 60% and 63% when compared to Berry-Ravindran in DNA, Protein and English text correspondingly. Moreover the rate of enhancement over Alpha Skip Search algorithm in DNA, Protein and English text are 48%, 28% and 36% respectively. Conclusion: The new proposed hybrid algorithm is relevant for searching biological science sequence database and also other string search systems.