A fast pattern matching algorithm for highly similar sequences

With the advent of NGS technologies there are more and more genomic sequences of individuals of the same species available. These sequences only differ by a very small amount. There is thus a strong need for efficient algorithms for performing fast pattern matching in such specific sets of sequences. In this paper we propose a very efficient algorithm that solves the on-line exact pattern matching problem in a set of highly similar DNA sequences. The algorithm we propose extends variants of the Boyer-Moore exact string matching algorithm. Experimental results show that our new algorithm exhibits the best performances in practice.