muBLASTP: database-indexed protein sequence search on multicore CPUs

BMC Bioinformatics

Software

Jing Zhang¹  Hao Wang¹  Wu-chun Feng¹  Sanchit Misra² 

[1] Department of Computer Science, Virginia Tech, 225 Stanger Street, 24060, Blacksburg, VA, USA;Parallel Computing Lab, Intel Corporation, Bengaluru, 560102, Karnataka, India;

关键词: BLAST;    Database index;    Local alignment;    Multicore;   

DOI  :  10.1186/s12859-016-1302-4

 received in 2016-02-09, accepted in 2016-10-21,  发布年份 2016

来源: Springer

【 摘 要 】

BackgroundThe 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.ResultsmuBLASTP, 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.ConclusionsWith 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.

【 授权许可】

CC BY   
© The Author(s) 2016

【 图 表 】

12864_2016_3440_Article_IEq55.gif

12864_2017_3669_Article_IEq5.gif

12864_2015_2295_Article_IEq3.gif