Some old and new ideas on efficient seeding for biosequence search

Gregory Kucherov, CNRS LIlle (France) and J.-V.Poncelet Lab, Moscow (Russia)

Abstract:

Since about 2002, spaced seeds and their different generalizations became an efficient tool for improving the performance of DNA sequence search. After presenting main ideas behind this technique, we briefly survey several extensions of spaced seeds proposed by different authors and allowing to further enhance the performance of the search. Then we present two new applications we developed recently: one for protein search and the other for mapping reads issued from a high-throughput sequencing technology to a reference genome.