Multiseed Lossless Filtration

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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [25 references]  Display  Hide  Download

https://hal.inria.fr/inria-00354810
Contributor : Gregory Kucherov <>
Submitted on : Wednesday, January 21, 2009 - 10:40:13 AM
Last modification on : Thursday, February 21, 2019 - 10:52:49 AM
Long-term archiving on : Tuesday, June 8, 2010 - 5:59:47 PM

Files

KucherovNoeRoytberg.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Gregory Kucherov, Laurent Noé, Mikhail Roytberg. Multiseed 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-00354810⟩

Share

Metrics

Record views

321

Files downloads

322