Improved BLAST searches using longer words for protein seeding.
BACKGROUND
The blastp and tblastn modules of BLAST are widely used methods for searching protein queries against protein and nucleotide databases, respectively. One heuristic used in BLAST is to consider only database sequences that contain a high-scoring match of length at most 5 to the query. We implemented the capability to use words of length 6 or 7. We demonstrate an improved trade-off between running time and retrieval accuracy, controlled by the score threshold used for short word matches. For example, the running time can be reduced by 20-30% while achieving ROC (receiver operator characteristic) scores similar to those obtained with current default parameters.


BACKGROUND
The option to use long words is in the NCBI C and C++ toolkit code for BLAST, starting with version 2.2.16 of blastall. A Linux executable used to produce the results herein is available at: ftp://ftp.ncbi.nlm.nih.gov/pub/agarwala/protein_longwords
Shiryev
Sergey A
SA
Department of Health and Human Services, National Center for Biotechnology Information, National Institutes of Health, Bethesda, MD, USA.
Papadopoulos
Jason S
JS
Schäffer
Alejandro A
AA
Agarwala
Richa
R
D000465:Algorithms; D003196:Computer Graphics; D003628:Database Management Systems; D030562:Databases, Protein; D016247:Information Storage and Retrieval / Q000379:methods*; D011506:Proteins / Q000737:chemistry* / Q000235:genetics*; D016415:Sequence Alignment / Q000379:methods*; D014584:User-Computer Interface
D011506:Proteins