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

Gregory Kucherov, Laurent Noé, Mikhail Roytberg

Research output: Contribution to journalArticlepeer-review

53 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)553-569
Number of pages17
JournalJournal of Bioinformatics and Computational Biology
Volume4
Issue number2
DOIs
Publication statusPublished - Apr 2006
Externally publishedYes

Keywords

  • Finite automaton
  • Sensitivity
  • Sequence alignment
  • Similarity search
  • Spaced seed
  • Subset seed

Fingerprint

Dive into the research topics of 'A unifying framework for seed sensitivity and its application to subset seeds'. Together they form a unique fingerprint.

Cite this