PLAST: parallel local alignment search tool for database comparison

Abstract

Background: Sequence similarity searching is an important and challenging task in molecular biology and next-generation sequencing should further strengthen the need for faster algorithms to process such vast amounts of data. At the same time, the internal architecture of current microprocessors is tending towards more parallelism, leading to the use of chips with two, four and more cores integrated on the same die. The main purpose of this work was to design an effective algorithm to fit with the parallel capabilities of modern microprocessors.

Results: A parallel algorithm for comparing large genomic banks and targeting middle-range computers has been developed and implemented in PLAST software. The algorithm exploits two key parallel features of existing and future microprocessors: the SIMD programming model (SSE instruction set) and the multithreading concept (multicore). Compared to multithreaded BLAST software, tests performed on an 8-processor server have shown speedup ranging from 3 to 6 with a similar level of accuracy.

Conclusion: A parallel algorithmic approach driven by the knowledge of the internal microprocessor architecture allows significant speedup to be obtained while preserving standard sensitivity for similarity search problems.

Figure 1

Bank indexing. Fragment of indexing scheme. For each seed key, a list of relative occurrence positions is stored on short integers.

Figure 2

Subsequence block. Fragment of subsequence block. For each seed key, a list of subsequences is constructed. Each subsequence contains a seed and its right and left neighborhood.

Figure 3

pseudocode for ungapped extension. The pseudocode of ungapped extension procedure for 2 blocks of subsequences. Sixteen extensions are simultaneously processed and a score is stored on an 8-bit unsigned byte integer.

Figure 4

pseudocode for small gapped extension. The pseudocode of small gapped extension procedure. Eight extensions are simultaneously processed and a score is stored on a 16-bit signed short integer.

Figure 5

ROC curve. (A) The ROC curves for the SCOP/ASTRAL40 data set of PLASTP and BLASTP. (B) The ROC curves for the Yeast data set of TPLASTN and TBLASTN. The ROC₁₀₀₀₀ score in (A) and ROC₂₅₀ score in (B) for each program are shown in parentheses after the program name.

Figure 6

Coverage versus error plot. (A) The coverage versus error plots for the SCOP/ASTRAL40 data set of PLASTP and BLASTP. (B) The coverage versus error plots for the Yeast data set of TPLASTN and TBLASTN.

Figure 7

Speedup of the three PLAST programs. Speedup of the three PLAST programs relative to the number of threads and data sets. The E-value cutoff is set to 10^-3.

Figure 8

PLAST profile. The profiles of the three PLAST programs, with and without SSE instructions. Each PLAST program was run with its specific data set: (A) PLASTP; (B) TPLASTN; (C) PLASTX.