Improvement of performance of MegaBlast algorithm for DNA sequence alignment

	Improvement of performance of MegaBlast algorithm for DNA sequence alignment
	Tan, Guang-Ming ; Xu, Lin ; Bu, Dong-Bo ; Feng, Sheng-Zhong ; Sun, Ning-Hui
	2006-11-01
发表期刊	JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY
ISSN	1000-9000
卷号	21 期号:6 页码:973-978
摘要	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.
关键词	sequence alignment BLAST MegaBlast I/O intensive parallelization
收录类别	SCI
语种	英语
WOS研究方向	Computer Science
WOS类目	Computer Science, Hardware & Architecture ; Computer Science, Software Engineering
WOS记录号	WOS:000242640200014
出版者	SCIENCE CHINA PRESS
引用统计	被引频次：4[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/10604
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Tan, Guang-Ming
作者单位	1.Chinese Acad Sci, Comp Technol Inst, Beijing 100080, Peoples R China 2.Grad Univ Chinese Acad Sci, Beijing 100039, Peoples R China
推荐引用方式 GB/T 7714	Tan, Guang-Ming,Xu, Lin,Bu, Dong-Bo,et al. Improvement of performance of MegaBlast algorithm for DNA sequence alignment[J]. JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY,2006,21(6):973-978.
APA	Tan, Guang-Ming,Xu, Lin,Bu, Dong-Bo,Feng, Sheng-Zhong,&Sun, Ning-Hui.(2006).Improvement of performance of MegaBlast algorithm for DNA sequence alignment.JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY,21(6),973-978.
MLA	Tan, Guang-Ming,et al."Improvement of performance of MegaBlast algorithm for DNA sequence alignment".JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY 21.6(2006):973-978.