An optimized algorithm of high spatial-temporal efficiency for Megablast

BLAST (basic local alignment search tool), as a heuristic algorithm, is one of the most widely used sequence similarity search tools. MegaBlast, as an improved version of BLAST, speeds up the searches and improves the total throughput owing to greedy algorithm and batch processing. However, MegaBlast consumes a great deal of memory, which is proportional to the product of the size of the query file and database file. This paper proposes an optimized MegaBlast algorithm based on MegaBlast. The new algorithm exchanges the query and subject sequences, and builds a hash table based on new subject sequences. The optimized algorithm overlaps I/O with computation, further decreases the overall time and the cost of memory, which is only proportional to the size of the database file. The optimized algorithm is suitable to be parallelized on cluster systems. As our experiments shown, the parallel program, which is implemented with MPI, achieves high speedup.