Estimating seed sensitivity on homogeneous alignments - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2003

Estimating seed sensitivity on homogeneous alignments

Laurent Noé
Yann Ponty

Résumé

We address the problem of measuring the sensitivity of seed-based similarity search algorithms. In contrast to approaches based on Markov models, we study the measurement based on homogeneous alignments. We describe an algorithm for counting and random generation of those alignments and an algorithm for exact computation of the sensitivity for a broad class of seed strategies. We provide experimental results demonstrating a bias introduced by ignoring the homogeneousness condition.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-5047.pdf (279.47 Ko) Télécharger le fichier

Dates et versions

inria-00071536 , version 1 (23-05-2006)

Identifiants

  • HAL Id : inria-00071536 , version 1

Citer

Gregory Kucherov, Laurent Noé, Yann Ponty. Estimating seed sensitivity on homogeneous alignments. [Research Report] RR-5047, INRIA. 2003, pp.17. ⟨inria-00071536⟩
104 Consultations
160 Téléchargements

Partager

Gmail Facebook X LinkedIn More