HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Multi-seed lossless filtration (Extended abstract)

Gregory Kucherov 1 Laurent Noé 1 Mikhail Roytberg 2
1 ADAGE - Applying discrete algorithms to genomics
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download

Contributor : Laurent Noé Connect in order to contact the contributor
Submitted on : Wednesday, March 22, 2006 - 9:33:29 PM
Last modification on : Friday, February 4, 2022 - 3:34:34 AM
Long-term archiving on: : Saturday, April 3, 2010 - 11:01:25 PM




Gregory Kucherov, Laurent Noé, Mikhail Roytberg. Multi-seed lossless filtration (Extended abstract). Proceedings of the 15th Annual Symposium on Combinatorial Pattern Matching - CPM'2004, Jul 2004, Istambul, Turkey. pp.297-310, ⟨10.1007/11557067_21⟩. ⟨inria-00001162⟩



Record views


Files downloads