Improvement of Performance of MegaBlast Algorithm for DNA Sequence Alignment |
| |
Authors: | Guang-Ming Tan Lin Xu Dong-Bo Bu Sheng-Zhong Feng Ning-Hui Sun |
| |
Affiliation: | 1Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100080, P.R. China ; 2 Graduate University of Chinese Academy of Sciences, Beijing 100039, P.R. China |
| |
Abstract: | MegaBlast is one of the most important programs in NCBI BLAST (Basic Local Alignment Search Tool) toolkits. However, MegaBlast is computation and I/O intensive. It consumes a great deal of memory which is proportional to the size of the query sequences set and subject (database) sequences set of product. This paper proposes a new strategy for optimizing MegaBlast. The new strategy exchanges the query and subject sequences sets, and builds a hash table based on new subject sequences. It overlaps I/O with computation, shortens the overall time and reduces the cost of memory, since the memory here is only proportional to the size of subject sequences set. The optimized algorithm is suitable to be parallelized in cluster systems. The parallel algorithm uses query segmentation method. As our experiments shown, the parallel program which is implemented with MPI has fine scalability. |
| |
Keywords: | sequence alignment BLAST MegaBlast I/O intensive parallelization |
本文献已被 CNKI 维普 万方数据 SpringerLink 等数据库收录! |
| 点击此处可从《计算机科学技术学报》浏览原始摘要信息 |
|
点击此处可从《计算机科学技术学报》下载全文 |