Multi-seed lossless filtration (Extended abstract)
- Resource Type
- Authors
- Kucherov, Gregory; Noé, Laurent; Roytberg, Mikhail
- Source
- Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching-CPM'2004
Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching-CPM'2004, Jul 2004, Istambul, Turkey. pp.297-310, ⟨10.1007/11557067_21⟩
- Subject
- lossless filtering : filtration
pattern matching
graines multiples
oligonucleotide design
[INFO.INFO-OH]Computer Science [cs]/Other [cs.OH]
conception d'oligonucleotide
filtrage sans perte
multi seed
- Language
- English
The original publication is available at www.springerlink.com; International audience; We study a method of seed-based lossless filtration for approximate string matching and related applications. The method is based on a simultaneous use of several spaced seeds rather than a single seed as studied by Burkhardt and Karkkainen [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.