Querying highly similar sequences. (1st January 2013) - Barton, Carl; Giraud, Mathieu; Iliopoulos, Costas S.; Lecroq, Thierry; Mouchard, Laurent; Pissis, Solon P.
In this paper, we present a solution to the extreme similarity sequencing problem. The extreme similarity sequencing problem consists of finding occurrences of a pattern p in a set S 0, S 1, …, S k, of sequences of equal length, where Si, for all 1≤i≤k, differs from S0 by a constant number of errors – around 10 in practice. We present an asymptotically fast O ( n + occ log occ ) time algorithm, as well as a practical O ( nk / w ) time algorithm for solving this problem, where n is the length of a sequence, occ is the number of candidate occurrences reported by our technique, w is the size of the machine word, and the total number of errors is bounded by k – the number of sequences.