Paper Abstract and Keywords |
Presentation |
2014-01-29 08:30
An Experimental Bit-Parallel Solution to Accelerate Smith-Waterman Algorithm Saori Sudo, Masato Yoshimi, Hidetsugu Irie, Tsutomu Yoshinaga (UEC) VLD2013-119 CPSY2013-90 RECONF2013-73 |
Abstract |
(in Japanese) |
(See Japanese page) |
(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) |
(in English) |
Smith-Waterman algorithm / bit-parallelism / / / / / / |
Reference Info. |
IEICE Tech. Rep., vol. 113, no. 417, CPSY2013-90, pp. 103-108, Jan. 2014. |
Paper # |
CPSY2013-90 |
Date of Issue |
2014-01-21 (VLD, CPSY, RECONF) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
Copyright and reproduction |
All rights are reserved and no part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. Notwithstanding, instructors are permitted to photocopy isolated articles for noncommercial classroom use without fee. (License No.: 10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
Download PDF |
VLD2013-119 CPSY2013-90 RECONF2013-73 |
Conference Information |
Committee |
IPSJ-SLDM CPSY RECONF VLD |
Conference Date |
2014-01-28 - 2014-01-29 |
Place (in Japanese) |
(See Japanese page) |
Place (in English) |
Hiyoshi Campus, Keio University |
Topics (in Japanese) |
(See Japanese page) |
Topics (in English) |
FPGA Applications, etc |
Paper Information |
Registration To |
CPSY |
Conference Code |
2014-01-SLDM-CPSY-RECONF-VLD |
Language |
Japanese |
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 |
Keyword(3) |
|
Keyword(4) |
|
Keyword(5) |
|
Keyword(6) |
|
Keyword(7) |
|
Keyword(8) |
|
1st Author's Name |
Saori Sudo |
1st Author's Affiliation |
The University of Electro-Communications (UEC) |
2nd Author's Name |
Masato Yoshimi |
2nd Author's Affiliation |
The University of Electro-Communications (UEC) |
3rd Author's Name |
Hidetsugu Irie |
3rd Author's Affiliation |
The University of Electro-Communications (UEC) |
4th Author's Name |
Tsutomu Yoshinaga |
4th Author's Affiliation |
The University of Electro-Communications (UEC) |
5th Author's Name |
|
5th Author's Affiliation |
() |
6th Author's Name |
|
6th Author's Affiliation |
() |
7th Author's Name |
|
7th Author's Affiliation |
() |
8th Author's Name |
|
8th Author's Affiliation |
() |
9th Author's Name |
|
9th Author's Affiliation |
() |
10th Author's Name |
|
10th Author's Affiliation |
() |
11th Author's Name |
|
11th Author's Affiliation |
() |
12th Author's Name |
|
12th Author's Affiliation |
() |
13th Author's Name |
|
13th Author's Affiliation |
() |
14th Author's Name |
|
14th Author's Affiliation |
() |
15th Author's Name |
|
15th Author's Affiliation |
() |
16th Author's Name |
|
16th Author's Affiliation |
() |
17th Author's Name |
|
17th Author's Affiliation |
() |
18th Author's Name |
|
18th Author's Affiliation |
() |
19th Author's Name |
|
19th Author's Affiliation |
() |
20th Author's Name |
|
20th Author's Affiliation |
() |
Speaker |
Author-1 |
Date Time |
2014-01-29 08:30:00 |
Presentation Time |
25 minutes |
Registration for |
CPSY |
Paper # |
VLD2013-119, CPSY2013-90, RECONF2013-73 |
Volume (vol) |
vol.113 |
Number (no) |
no.416(VLD), no.417(CPSY), no.418(RECONF) |
Page |
pp.103-108 |
#Pages |
6 |
Date of Issue |
2014-01-21 (VLD, CPSY, RECONF) |
|