FASTPAT - A FAST AND EFFICIENT ALGORITHM FOR STRING SEARCHING IN DNA-SEQUENCES

A new string searching algorithm is Presented aimed at searching for t he occurrence of character patterns in longer character texts. The alg orithm, specifically designed for nucleic acid sequence data, is essen tially derived from the Boyer-Moore method (Comm. ACM, 20, 762-772, 19 77). Both pattern and text data are compressed so that the natural 4-l etter alphabet of nucleic acid sequences is considerably enlarged. The string search starts from the last character of the pattern and proce eds in large jumps through the text to be searched. The data compressi on and searching algorithm allows one to avoid searching for patterns not present in the text as well as to inspect, for each pattern, all t ext characters until the exact match with the text is found. These con siderations are supported by empirical evidence and comparisons with o ther methods.