Improved hit criteria for DNA local alignment.

by: L Noé, G Kucherov

BMC Bioinformatics, Vol. 5 (14 October 2004)

View FullText article

DOI, Pubmed, Hubmed

Reviews [Write a review of this article]

There are no reviews of this article

Find related articles from these CiteULike users

umit, AaronDarling, timflutre, nedwards, bozdagd, treangen

Find related articles with these CiteULike tags

algorithm, alignment, bioinformatics, gapped-seeds, local-alignment, no-tag, sequence-alignment, sequencing, string-matching, subset-seeds, wabi, yass04

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/.

@article{citeulike:622625, 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/.}, address = {LORIA/INRIA-Lorraine, Villers-l\`{e}s-Nancy France. Laurent.Noe@loria.fr}, author = {No\'{e}, L. and Kucherov, G. }, citeulike-article-id = {622625}, doi = {http://dx.doi.org/10.1186/1471-2105-5-149}, issn = {1471-2105}, journal = {BMC Bioinformatics}, month = {October}, posted-at = {2008-05-30 11:17:01}, priority = {3}, title = {Improved hit criteria for DNA local alignment.}, url = {http://dx.doi.org/10.1186/1471-2105-5-149}, volume = {5}, year = {2004} }

RIS record

TY - JOUR ID - citeulike:622625 L3 - citeulike-article-id:622625 TI - Improved hit criteria for DNA local alignment. JF - BMC Bioinformatics VL - 5 AD - LORIA/INRIA-Lorraine, Villers-lès-Nancy France. Laurent.Noe@loria.fr SN - 1471-2105 N2 - 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/. AU - Noé, L AU - Kucherov, G PY - 2004/10/14/ UR - http://dx.doi.org/10.1186/1471-2105-5-149 ER -

RIS BibTeX