Multiple Sequence Alignment Based on Dynamic Programming Using FPGA

Shingo MASUNO  Tsutomu MARUYAMA  Yoshiki YAMAGUCHI  Akihiko KONAGAYA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E90-D   No.12   pp.1939-1946
Publication Date: 2007/12/01
Online ISSN: 1745-1361
DOI: 10.1093/ietisy/e90-d.12.1939
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Reconfigurable Systems)
Category: Reconfigurable System and Applications
Keyword: 
multiple sequence alignment,  dynamic programming,  FPGA,  reconfiguration,  

Full Text: PDF(436.1KB)>>
Buy this Article




Summary: 
Multiple sequence alignment problems in computational biology have been focused recently because of the rapid growth of sequence databases. By computing alignment, we can understand similarity among the sequences. Many hardware systems for alignment have been proposed to date, but most of them are designed for two-dimensional alignment (alignment between two sequences) because of the complexity to calculate alignment among more than two sequences under limited hardware resources. In this paper, we describe a compact system with an off-the-shelf FPGA board and a host computer for more than three-dimensional alignment based on dynamic programming. In our approach, high performance is achieved (1) by configuring optimal circuit for each dimensional alignment, and (2) by two phase search in each dimension by reconfiguration. In order to realize multidimensional search with a common architecture, two-dimensional dynamic programming is repeated along other dimensions. With this approach, we can minimize the size of units for alignment and achieve high parallelism. Our system with one XC2V6000 enables about 300-fold speedup as compared with single Intel Pentium4 2 GHz processor for four-dimensional alignment, and 100-fold speedup for five-dimensional alignment.