Title :
Design and Implementation of a Highly Parameterised FPGA-Based Skeleton for Pairwise Biological Sequence Alignment
Author :
Benkrid, Khaled ; Liu, Ying ; Benkrid, Abdsamad
Author_Institution :
Edinburgh Univ., Edinburgh
Abstract :
This paper presents the design and implementation of a generic and highly parameterised FPGA-based skeleton for pairwise biological sequence alignment. The skeleton is parameterised in terms of the sequence symbol type i.e. DNA, RNA, or protein sequences, the sequence lengths, the match score i.e. the score attributed to a symbol match or the penalty attributed to a mismatch or gap, and the matching task. Instances of the skeleton implement the Smith-Waterman and the Needleman-Wunsch algorithms. The skeleton has been captured in the Handel-C language which makes it FPGA-platform-independent. It implements the sequence alignment algorithm in hand using a pipeline of basic processing elements, which are tailored to the supplied parameters. Actual hardware implementations of the Smith-Waterman algorithm for protein sequence alignment achieve speed-ups in excess of 100:1 compared to equivalent standard desktop software implementations.
Keywords :
biology computing; field programmable gate arrays; molecular biophysics; proteins; sequences; Handel-C language; Needleman-Wunsch algorithm; Smith-Waterman algorithm; highly parameterised FPGA-based skeleton; pairwise biological sequence alignment; protein sequence; Biological information theory; Biology computing; DNA; Databases; Field programmable gate arrays; Hardware; Pipelines; Protein engineering; Sequences; Skeleton;
Conference_Titel :
Field-Programmable Custom Computing Machines, 2007. FCCM 2007. 15th Annual IEEE Symposium on
Conference_Location :
Napa, CA
Print_ISBN :
978-0-7695-2940-0
DOI :
10.1109/FCCM.2007.6