Estimating seed sensitivity on homogeneous alignments

Gregory Kucherov 1 Laurent Noé 1 Yann Ponty
1 ADAGE - Applying discrete algorithms to genomics
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : 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.
Document type :
[Research Report] RR-5047, INRIA. 2003, pp.17
Liste complète des métadonnées
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 5:53:05 PM
Last modification on : Tuesday, March 6, 2018 - 5:40:55 PM
Document(s) archivé(s) le : Sunday, April 4, 2010 - 10:23:33 PM


  • HAL Id : inria-00071536, version 1



Gregory Kucherov, Laurent Noé, Yann Ponty. Estimating seed sensitivity on homogeneous alignments. [Research Report] RR-5047, INRIA. 2003, pp.17. 〈inria-00071536〉



Record views


Files downloads