title: Querying highly similar sequences.
abstract: 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 S(i), for all 1≤i≤k, differs from S(0) by a constant number of errors - around 10 in practice. We present an asymptotically fast O(n + occ logocc) 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.
authors: Department of Informatics, King's College London, London, UK. carl.barton@kcl.ac.uk
authors: Carl
authors: C
authors: Barton
authors: Mathieu
authors: M
authors: Giraud
authors: Costas S
authors: CS
authors: Iliopoulos
authors: Thierry
authors: T
authors: Lecroq
authors: Laurent
authors: L
authors: Mouchard
authors: Solon P
authors: SP
authors: Pissis
mesh_terms: D000465:Algorithms; D019295:Computational Biology; D059014:High-Throughput Nucleotide Sequencing; D017422:Sequence Analysis, DNA / Q000379:methods*; D012689:Sequence Homology, Nucleic Acid