计算机科学与探索 ›› 2008, Vol. 2 ›› Issue (5): 519-528.DOI: 10.3778/j.issn.1673-9418.2008.05.007

• 学术研究 • 上一篇    下一篇

生物信息学双序列比对算法加速器设计与实现

张 阳+,窦 勇,夏 飞   

  1. 国防科学技术大学 计算机学院,长沙 410073
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2008-10-06 发布日期:2008-10-06
  • 通讯作者: 张 阳

Design and implementation of bioinformatics pare-wise alignment accelerator

ZHANG Yang+, DOU Yong, XIA Fei   

  1. School of Computer Science, National University of Defense Technology, Changsha 410073, China
  • Received:1900-01-01 Revised:1900-01-01 Online:2008-10-06 Published:2008-10-06
  • Contact: ZHANG Yang

摘要: 双序列比对算法是进行生物信息学研究的基础算法。在FPGA上实现大规模脉动式阵列对双序列比对算法进行加速能够大幅度提高比对的效率。然而现有的设计方法在比对序列长度较短的情况下,处理单元利用率很低;在序列的长度较大时,需要占用大量的片内存储资源。通过将两条序列同时送入阵列进行比对减少比对时间。将比对数据送入外部存储器,优化比对过程中的数据存储调度,有效降低了对片内存储器的需求。以Smith-Waterman算法为例进行了实现验证,结果表明本设计在性能上优于传统设计。与Pentium4 2.60 GHz通用微处理器计算机相比,使用加速器对长度为65 536的序列进行比对可获得1 555倍的加速比。

关键词: 双序列比对, 现场可编程门阵列, 硬件加速, 脉动式阵列, Smith-Waterman算法

Abstract: Pare-wise alignment is a basal algorithm of bioinformatics research. Implementing large scale of systolic array in FPGA to accelerate pare-wise alignment can improve the efficiency of alignment remarkably. However, the existing designs’ utilization of process element is very low when sequences are short, while a large number of internal storage resources would be demanded when sequences are long. The alignment time is reduced by sending the two sequences to systolic array simultaneously. The requirement of internal storage is decreased effectively by sending alignment data to external storage and optimizing the data schedule. The Smith-Waterman algorithm is implemented as an example. The experiments show that this design is superior to traditional ways. Comparing to P4 2.60 GHz host computer,this design can achieve 1 555 speedup for 65 536-residue sequences.

Key words: pair-wise alignment, Field Programmable Gate Array (FPGA), hardware acceleration, systolic array, Smith-Waterman algorithm