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

A unifying framework for seed sensitivity and its application to subset seeds

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 propose a general approach to compute the seed sensitivity, that can be applied to different definitions of seeds. It treats separately three components of the seed sensitivity problem -- a set of target alignments, an associated probability distribution, and a seed model -- that are specified by distinct finite automata. The approach is then applied to a new concept of subset seeds for which we propose an efficient automaton construction. Experimental results confirm that sensitive subset seeds can be efficiently designed using our approach, and can then be used in similarity search producing better results than ordinary spaced seeds.
Document type :
Complete list of metadata

Cited literature [25 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Friday, May 19, 2006 - 9:03:08 PM
Last modification on : Friday, February 4, 2022 - 3:30:49 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:36:29 PM


  • HAL Id : inria-00070629, version 1



Gregory Kucherov, Laurent Noé, Mikhail Roytberg. A unifying framework for seed sensitivity and its application to subset seeds. [Research Report] RR-5374, INRIA. 2004, pp.21. ⟨inria-00070629⟩



Record views


Files downloads