Abstract: MegaBlast is one of the most important programs in NCBIBLAST (Basic Local Alignment Search Tool) toolkits. However, MegaBlastis computation and I/O intensive. It consumes a great deal of memorywhich is proportional to the size of the query sequencesset and subject (database) sequences set of product. This paper proposes a newstrategy for optimizing MegaBlast. The new strategy exchanges the queryand subject sequences sets, and builds a hash table based on newsubject sequences. It overlaps I/O with computation, shortensthe overall time and reduces the cost of memory, since the memory hereis only proportional to the size of subject sequences set. The optimizedalgorithm is suitable to be parallelized in cluster systems. Theparallel algorithm uses query segmentation method. As our experimentsshown, the parallel program which is implemented with MPI has finescalability.