Compressed indexes for approximate string matching

Abstract

We revisit the problem of indexing a string 5[1.n] to support searching all substrings in S that match a given pattern P[1.m] with at most k errors. Previous solutions either require an index of size exponential in k or need Ω(m k) time for searching. Motivated by the indexing of DNA sequences, we investigate space efficient indexes that occupy only O(n) space. For k = 1, we give an index to support matching in O(m+occ+lognloglogn) time. The previously best solution achieving this time complexity requires an index of size O(n log n). This new index can be used to improve existing indexes for k ≥ 2 errors. Among others, it can support matching with k = 2 errors in O(m log n log log n + occ) time. © Springer-Verlag Berlin Heidelberg 2006.