Skip to Main content Skip to Navigation
New interface
Reports (Research report)

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)
Complete list of metadata
Contributor : Rapport De Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 5:53:05 PM
Last modification on : Wednesday, October 26, 2022 - 8:16:10 AM
Long-term archiving on: : 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