Multi-seed lossless filtration

Gregory Kucherov (1) , Laurent Noé (1) , Mikhail Roytberg

1 ADAGE - Applying discrete algorithms to genomics

We study a method of seed-based lossless filtration for approximate string matching and related bioinformatics applications. The method is based on a simultaneous use of several spaced seeds rather than a single seed as studied by Burkhardt and Kärkkäinen [1]. We present algorithms to compute several important parameters of seed families, study their combinatorial properties, and describe several techniques to construct efficient families. We also report a large-scale application of the proposed technique to the problem of oligonucleotide selection for an EST sequence database.

Mots clés: filtration; string matching; gapped seed; gapped q-gram; local alignment; sequence similarity; seed family; multiple spaced seeds; dynamic programming; est; oligonucleotide selection

Domaines: Algorithme et structure de données [cs.DS]

Gregory Kucherov, Laurent Noé, Mikhail Roytberg. Multi-seed lossless filtration. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2005, 2 (1), pp.51--61. ⟨10.1109/TCBB.2005.12⟩. ⟨inria-00000718⟩