Multiple Filtration and Approximate Pattern Matching’

P. A. Pe~zner’. ~ and M. S. water ma^^'.^ Abstract. Given a text of length n and a query of length q, we present an algorithm for finding all locations of m-tuples in the text and in the query that differ by at most k mismatches. This problem is motivated by the dot-matrix constructions for sequence comparison and optimal oligonucleotide probe selection routinely used in molecular biology. In the case q = m the problem coincides with the classical approximate string matching with k mismatches problem. We present a new approach to this problem based on multiple hashing, which may have advantages over some sophisticated and theoretically efficient methods that have been proposed. This paper describes a two-stage process. The first stage (multiple filtration) uses a new technique to preselect roughly similar m-tuples. The second stage compares these m-tuples using an accurate method. We demonstrate the advantages of multiple filtration in comparison with other techniques for approximate pattern matching. Key Wok String matching, Computational molecular biology. 1. Introduction. Suppose we are given a string of length n, T[1*. n], called the text, a shorter string of length q, Q[1-*-q], called the query, and integers k and m. The substring matching problem with k-mismatches [CL] is to find all “starting