Presentation | 2014-01-29 An Experimental Bit-Parallel Solution to Accelerate Smith-Waterman Algorithm Saori SUDO, Masato YOSHIMI, Hidetsugu IRIE, Tsutomu YOSHINAGA, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | The Smith-Waterman (SW) algorithm is a computational method to obtain well accorded subsequences between two strings, and is widely used in a similarity retrieval for genome and amino acid sequences. A lot of effort has been done to accelerate the algorithm, especially new solutions which efficiently utilize recent hardware accelerators are promising. Several dynamic programming based algorithms, such as edit distance and the longest common subsequence, are solved by fast bit-parallelized algorithms. This paper proposes a new bit-parallelization scheme for the SW algorithm. By utilizing a technique of evolutionary computation, calculation formulae from input bit-vectors to output bit-vectors are discovered for an abridged version of the SW algorithm which constrained parameters. We evaluate performance based on the obtained formulae and discuss feasibility of the proposed bit parallel SW algorithm. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | Smith-Waterman algorithm / bit-parallelism |
Paper # | VLD2013-119,CPSY2013-90,RECONF2013-73 |
Date of Issue |
Conference Information | |
Committee | RECONF |
---|---|
Conference Date | 2014/1/21(1days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | |
Vice Chair | |
Secretary | |
Assistant |
Paper Information | |
Registration To | Reconfigurable Systems (RECONF) |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | An Experimental Bit-Parallel Solution to Accelerate Smith-Waterman Algorithm |
Sub Title (in English) | |
Keyword(1) | Smith-Waterman algorithm |
Keyword(2) | bit-parallelism |
1st Author's Name | Saori SUDO |
1st Author's Affiliation | Graduate School of Information Systems, The University of Electro-Communications() |
2nd Author's Name | Masato YOSHIMI |
2nd Author's Affiliation | Graduate School of Information Systems, The University of Electro-Communications |
3rd Author's Name | Hidetsugu IRIE |
3rd Author's Affiliation | Graduate School of Information Systems, The University of Electro-Communications |
4th Author's Name | Tsutomu YOSHINAGA |
4th Author's Affiliation | Graduate School of Information Systems, The University of Electro-Communications |
Date | 2014-01-29 |
Paper # | VLD2013-119,CPSY2013-90,RECONF2013-73 |
Volume (vol) | vol.113 |
Number (no) | 418 |
Page | pp.pp.- |
#Pages | 6 |
Date of Issue |