A reconfigurable accelerator for Smith-Waterman algorithm

doi:10.1109/TCSII.2007.909857

	A reconfigurable accelerator for Smith-Waterman algorithm
	Jiang, Xianyang 1,2; Liu, Xinchun 1; Xu, Lin 1; Zhang, Peiheng 1; Sun, Ninghui 1
	2007-12-01
发表期刊	IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS II-EXPRESS BRIEFS
ISSN	1549-7747
卷号	54 期号:12 页码:1077-1081
摘要	Scanning bio-sequence database and finding similarities among DNA and protein sequences is basic and important work in bioinformatics field. To solve this problem, Needleman-Wunschh (NW) algorithm is a classical and precise tool, and Smith-Waterman (SW) algorithm is more practical for its capability to find similarities between subsequences. Such algorithms have computational complexity proportional to the length product of both involved sequences, hence processing time becomes insufferable due to exponential growth speed and great amount of bio-sequence database. To alleviate this serious problem, a reconfigurable accelerator for SW algorithm is presented. In the accelerator, a modified equation is proposed to improve mapping efficiency of a processing element (PE), and a special floor plan is applied to a fine-grain parallel PE array and interface components to cut down their routing delay. Basing on the two techniques, the proposed accelerator can reach at 82-MHz frequency in an Altera EP1S30 device. Experiments demonstrate the accelerator provides more than 330 speedup as compared to a standard desktop platform with a 2.8-GHz Xeon processor and 4-GB memory and has 50% improvement on the peak performance of a transferred traditional implementation without using the two special techniques. Our implementation is also about 9% faster than the fastest implementation in a most recent family of SW algorithm accelerators.
关键词	bioinformatics computational complexity field-programmable gate array (FPGA) reconfigurable accelerator Smith-Waterman (SW) algorithm
DOI	10.1109/TCSII.2007.909857
收录类别	SCI
语种	英语
WOS研究方向	Engineering
WOS类目	Engineering, Electrical & Electronic
WOS记录号	WOS:000251944900011
出版者	IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
引用统计	被引频次：41[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/11011
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Jiang, Xianyang
作者单位	1.Chinese Acad Sci, Inst Comp Technol, Key Lab Comp Syst & Architecture, Beijing 100080, Peoples R China 2.Wuhan Univ, Inst Microelect & Informat Technol, Wuhan 430072, Peoples R China
推荐引用方式 GB/T 7714	Jiang, Xianyang,Liu, Xinchun,Xu, Lin,et al. A reconfigurable accelerator for Smith-Waterman algorithm[J]. IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS II-EXPRESS BRIEFS,2007,54(12):1077-1081.
APA	Jiang, Xianyang,Liu, Xinchun,Xu, Lin,Zhang, Peiheng,&Sun, Ninghui.(2007).A reconfigurable accelerator for Smith-Waterman algorithm.IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS II-EXPRESS BRIEFS,54(12),1077-1081.
MLA	Jiang, Xianyang,et al."A reconfigurable accelerator for Smith-Waterman algorithm".IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS II-EXPRESS BRIEFS 54.12(2007):1077-1081.