Multi-seed lossless filtration

Gregory Kucherov, Laurent Noé, Mikhail Roytberg

Research output: Contribution to journalArticlepeer-review

13 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)297-310
Number of pages14
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3109
Publication statusPublished - 2004
Externally publishedYes

Fingerprint

Dive into the research topics of 'Multi-seed lossless filtration'. Together they form a unique fingerprint.

Cite this