IEICE TRANSACTIONS on Information
Multiple Sequence Alignment Based on Dynamic Programming Using FPGA
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E90-D No.12 pp.1939-1946
- Publication Date
- 2007/12/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1093/ietisy/e90-d.12.1939
- Type of Manuscript
- Special Section PAPER (Special Section on Reconfigurable Systems)
- Category
- Reconfigurable System and Applications
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Shingo MASUNO, Tsutomu MARUYAMA, Yoshiki YAMAGUCHI, Akihiko KONAGAYA, "Multiple Sequence Alignment Based on Dynamic Programming Using FPGA" in IEICE TRANSACTIONS on Information,
vol. E90-D, no. 12, pp. 1939-1946, December 2007, doi: 10.1093/ietisy/e90-d.12.1939.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e90-d.12.1939/_p
Copy
@ARTICLE{e90-d_12_1939,
author={Shingo MASUNO, Tsutomu MARUYAMA, Yoshiki YAMAGUCHI, Akihiko KONAGAYA, },
journal={IEICE TRANSACTIONS on Information},
title={Multiple Sequence Alignment Based on Dynamic Programming Using FPGA},
year={2007},
volume={E90-D},
number={12},
pages={1939-1946},
abstract={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.},
keywords={},
doi={10.1093/ietisy/e90-d.12.1939},
ISSN={1745-1361},
month={December},}
Copy
TY - JOUR
TI - Multiple Sequence Alignment Based on Dynamic Programming Using FPGA
T2 - IEICE TRANSACTIONS on Information
SP - 1939
EP - 1946
AU - Shingo MASUNO
AU - Tsutomu MARUYAMA
AU - Yoshiki YAMAGUCHI
AU - Akihiko KONAGAYA
PY - 2007
DO - 10.1093/ietisy/e90-d.12.1939
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E90-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2007
AB - 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.
ER -
English
