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
Journal articles

Multi-seed lossless filtration

Gregory Kucherov 1 Laurent Noé 1 Mikhail Roytberg
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 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.
Keywords : filtration string matching gapped seed gapped q-gram local alignment sequence similarity seed family multiple spaced seeds dynamic programming est oligonucleotide selection
Document type :
Journal articles
Complete list of metadata
https://hal.inria.fr/inria-00000718
Contributor : Gregory Kucherov Connect in order to contact the contributor
Submitted on : Tuesday, November 15, 2005 - 12:45:16 PM
Last modification on : Friday, February 4, 2022 - 3:30:00 AM

Links full text

arxiv

Identifiers

Collections

INRIA | CNRS | LORIA | UNIV-LORRAINE | INRIA2

Citation

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

Export

BibTeX TEI DC DCterms EndNote Datacite

Share

Metrics

Record views

60

 

Contact                    Legal Notice                    Personal Data