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 :
Reports
[Research Report] RR-5047, INRIA. 2003, pp.17
Liste complète des métadonnées

https://hal.inria.fr/inria-00071536
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 5:53:05 PM
Last modification on : Tuesday, October 25, 2016 - 4:57:20 PM
Document(s) archivé(s) le : Sunday, April 4, 2010 - 10:23:33 PM

Identifiers

  • HAL Id : inria-00071536, version 1

Collections

Citation

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

Share

Metrics

Record views

206

Document downloads

136