HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

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 : BACKGROUND: 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. RESULTS: 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. CONCLUSIONS: Proposed algorithmic ideas allow to obtain a significant gain in sensitivity of similarity search without increase in execution time. The method has been implemented in YASS software available at http://www.loria.fr/projects/YASS/.
Complete list of metadata

Contributor : Laurent Noé Connect in order to contact the contributor
Submitted on : Monday, January 25, 2010 - 7:22:47 PM
Last modification on : Friday, February 4, 2022 - 3:30:01 AM

Links full text




Laurent Noé, Gregory Kucherov. Improved hit criteria for DNA local alignment.. BMC Bioinformatics, BioMed Central, 2004, 5 (149), pp.1-9. ⟨10.1186/1471-2105-5-149⟩. ⟨inria-00448743⟩



Record views