inria-00071536, version 1
Estimating seed sensitivity on homogeneous alignments
Gregory Kucherov 1Laurent Noé
1Yann Ponty
N° RR-5047 (2003)
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.
- 1: ADAGE (INRIA Lorraine - LORIA)
- INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)
- Domain : Computer Science/Other
- Keywords : local alignment – sensibility – spaced seeds – maximal scoring pair – msp – high scoring pair – hsp
- Internal note : RR-5047
- inria-00071536, version 1
- http://hal.inria.fr/inria-00071536
- oai:hal.inria.fr:inria-00071536
- From: Rapport De Recherche Inria
- Submitted on: Tuesday, 23 May 2006 17:53:05
- Updated on: Friday, 23 June 2006 09:43:27
Associated documents
Export