muBLASTP: database-indexed protein sequence search on multicore CPUs

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics and Proteomics

Background:

• The Basic Local Alignment Search Tool (BLAST) is crucial for sequence similarity searches in life sciences.
• Current NCBI BLAST uses a query-indexed approach, which is sensitive but can be slow.
• Existing database-indexed methods offer higher throughput but often lack the sensitivity of NCBI BLAST or are limited to nucleotide searches.

Purpose of the Study:

• To develop a novel database-indexed BLAST algorithm for protein sequence search.
• To achieve higher throughput comparable to other database-indexed methods while maintaining the sensitivity of NCBI BLAST.
• To optimize the BLASTP algorithm for modern multicore processors.

Main Methods:

• Developed a new index structure tailored for protein databases.
• Re-factored the BLASTP algorithm to leverage database indexing.
• Implemented optimizations for modern multicore CPU architectures.

Main Results:

• The novel muBLASTP achieves identical search results to NCBI BLAST.
• Single-threaded muBLASTP shows up to 1.75-fold end-to-end speedup over single-threaded NCBI BLAST.
• Multi-threaded muBLASTP demonstrates up to 4.56-fold end-to-end speedup over multi-threaded NCBI BLAST on Intel Haswell CPUs.

Conclusions:

• muBLASTP offers significantly improved throughput for protein sequence searches.
• The new approach maintains the high sensitivity of NCBI BLAST.
• The re-factored BLASTP algorithm is efficient on modern multicore processors with a manageable memory footprint.