muBLASTP: database-indexed protein sequence search on multicore CPUs.
BACKGROUND
The Basic Local Alignment Search Tool (BLAST) is a fundamental program in the life sciences that searches databases for sequences that are most similar to a query sequence. Currently, the BLAST algorithm utilizes a query-indexed approach. Although many approaches suggest that sequence search with a database index can achieve much higher throughput (e.g., BLAT, SSAHA, and CAFE), they cannot deliver the same level of sensitivity as the query-indexed BLAST, i.e., NCBI BLAST, or they can only support nucleotide sequence search, e.g., MegaBLAST. Due to different challenges and characteristics between query indexing and database indexing, the existing techniques for query-indexed search cannot be used into database indexed search.


RESULTS
muBLASTP, a novel database-indexed BLAST for protein sequence search, delivers identical hits returned to NCBI BLAST. On Intel Haswell multicore CPUs, for a single query, the single-threaded muBLASTP achieves up to a 4.41-fold speedup for alignment stages, and up to a 1.75-fold end-to-end speedup over single-threaded NCBI BLAST. For a batch of queries, the multithreaded muBLASTP achieves up to a 5.7-fold speedups for alignment stages, and up to a 4.56-fold end-to-end speedup over multithreaded NCBI BLAST.


CONCLUSIONS
With a newly designed index structure for protein database and associated optimizations in BLASTP algorithm, we re-factored BLASTP algorithm for modern multicore processors that achieves much higher throughput with acceptable memory footprint for the database index.
Department of Computer Science, Virginia Tech, 225 Stanger Street, Blacksburg, 24060, VA, USA. zjing14@vt.edu.
Jing
J
Zhang
Parallel Computing Lab, Intel Corporation, Bengaluru, Karnataka, 560102, India.
Sanchit
S
Misra
Department of Computer Science, Virginia Tech, 225 Stanger Street, Blacksburg, 24060, VA, USA.
Hao
H
Wang
Department of Computer Science, Virginia Tech, 225 Stanger Street, Blacksburg, 24060, VA, USA.
Wu-Chun
WC
Feng
D000465:Algorithms; D030562:Databases, Protein; D006801:Humans; D016247:Information Storage and Retrieval / Q000379:methods*; D011506:Proteins / Q000737:chemistry*; D016415:Sequence Alignment / Q000379:methods*; D020539:Sequence Analysis, Protein / Q000379:methods*; D012984:Software; D014584:User-Computer Interface
D011506:Proteins
BLAST; Database index; Local alignment; Multicore