Querying highly similar sequences. (1st January 2013)

• Record Type: Journal Article
• Authors: Barton, Carl; Giraud, Mathieu; Iliopoulos, Costas S.; Lecroq, Thierry; Mouchard, Laurent; Pissis, Solon P.
• Is Part Of: International journal of computational biology and drug design. Volume 6:Number 1/2(2013)
• Page Start: 119
• Page End: 130
• Publication Date: 2013-01-01
• Subjects: DNA sequencing -- highly similar sequences -- similarity searching -- querying DNA sequences -- NGS -- next-generation sequencing; Computational biology -- Periodicals; Drugs -- Design -- Periodicals; 570.285
• Languages: English
• ISSNs: 1756-0756

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 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.