Improved hit criteria for DNA local alignment

Laurent Noé 1 Gregory Kucherov 1
1 ADAGE - Applying discrete algorithms to genomics
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : The hit criterion is a key component of heuristic local alignment algorithms. It specifies a class of patterns assumed to witness a potential similarity, and this choice is decisive for the selectivity and sensitivity of the whole method. In this paper, we propose two ways to improve the hit criterion. First, we define the group criterion combining the advantages of the single-seed and double-seed approaches used in existing algorithms. Second, we introduce transition-constrained seeds that extend spaced seeds by the possibility of distinguishing transition and transversion mismatches. We provide analytical data as well as experimental results, obtained with the YASS software, supporting both improvements.
Type de document :
Communication dans un congrès
Proceedings of the 5th Open Days in Biology, Computer Science and Mathematics - JOBIM'2004, 2004, Montreal, Canada, 11 p, 2004
Liste complète des métadonnées

https://hal.inria.fr/inria-00099999
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 10:13:17
Dernière modification le : mardi 6 mars 2018 - 17:40:55

Identifiants

  • HAL Id : inria-00099999, version 1

Collections

Citation

Laurent Noé, Gregory Kucherov. Improved hit criteria for DNA local alignment. Proceedings of the 5th Open Days in Biology, Computer Science and Mathematics - JOBIM'2004, 2004, Montreal, Canada, 11 p, 2004. 〈inria-00099999〉

Partager

Métriques

Consultations de la notice

151