MULTIPLE FILTRATION AND APPROXIMATE PATTERN-MATCHING

Given a text of length n and a query of length q, we present an algori thm 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 oligonuc leotide probe selection routinely used in molecular biology. In the ca se q = m the problem coincides with the classical approximate string m atching with k mismatches problem. We present a new approach to this p roblem based on multiple hashing, which may have advantages over some sophisticated and theoretically efficient methods that have been propo sed. This paper describes a two-stage process. The first stage (multip le filtration) uses a new technique to preselect roughly similar m-tup les. The second stage compares these In-tuples using an accurate metho d. We demonstrate the advantages of multiple filtration in comparison with other techniques for approximate pattern matching.