| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2014-01-29 08:30 Smith-Watermanアルゴリズム向けビット並列手法の検討 ○須戸里織・吉見真聡・入江英嗣・吉永 努（電通大）  VLD2013-119 CPSY2013-90 RECONF2013-73 |
|
| 抄録 | （和） | Smith-Waterman（SW）アルゴリズムは，2つの文字列からよく一致する部分文字列を探索する計算手法であり，遺伝子やアミノ酸配列の配列類似性検索に広く応用されている． SW法の高速化に関する様々な取り組みが行われているなかでも，演算効率を向上させるアルゴリズムの開発は，アクセラレータでの実行で大きな効果が期待できる． SWアルゴリズムと同様に動的計画法で計算を行う編集距離や最長共通部分列(LCS)問題では，アルゴリズムをビットベクトル同士の演算で実現するビット並列化が提案されており，並列度の大きな向上が報告されている． 本研究報告では，SWアルゴリズムのビット並列化について議論する． パラメータに制約のある簡略版のSW法を対象に，ブロック単位の入出力をビットベクトルで列挙し， 入出力間の演算を進化的計算を用いて発見した． 得られた論理式を元に速度評価を行い，ビット並列SWアルゴリズムの実現可能性について議論する． |
| （英） | 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. |
|
| キーワード | （和） | Smith-Watermanアルゴリズム / ビット並列性 / / / / / / |
| （英） | Smith-Waterman algorithm / bit-parallelism / / / / / / | |
| 文献情報 | 信学技報, vol. 113, no. 417, CPSY2013-90, pp. 103-108, 2014年1月. | |
| 資料番号 | CPSY2013-90 | |
| 発行日 | 2014-01-21 (VLD, CPSY, RECONF) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | VLD2013-119 CPSY2013-90 RECONF2013-73 |
|
| 研究会情報 | |
| 研究会 | IPSJ-SLDM CPSY RECONF VLD |
| 開催期間 | 2014-01-28 - 2014-01-29 |
| 開催地（和） | 慶応義塾大学 日吉キャンパス |
| 開催地（英） | Hiyoshi Campus, Keio University |
| テーマ（和） | FPGA応用および一般 |
| テーマ（英） | FPGA Applications, etc |
| 講演論文情報の詳細 | |
| 申込み研究会 | CPSY |
| 会議コード | 2014-01-SLDM-CPSY-RECONF-VLD |
| 本文の言語 | 日本語 |
| タイトル（和） | Smith-Watermanアルゴリズム向けビット並列手法の検討 |
| サブタイトル（和） | |
| タイトル（英） | An Experimental Bit-Parallel Solution to Accelerate Smith-Waterman Algorithm |
| サブタイトル（英） | |
| キーワード(1)（和/英） | Smith-Watermanアルゴリズム / Smith-Waterman algorithm |
| キーワード(2)（和/英） | ビット並列性 / bit-parallelism |
| キーワード(3)（和/英） | / |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 須戸 里織 / Saori Sudo / スド サオリ |
| 第1著者 所属（和/英） | 電気通信大学 (略称： 電通大) The University of Electro-Communications (略称： UEC) |
| 第2著者 氏名（和/英/ヨミ） | 吉見 真聡 / Masato Yoshimi / ヨシミ マサト |
| 第2著者 所属（和/英） | 電気通信大学 (略称： 電通大) The University of Electro-Communications (略称： UEC) |
| 第3著者 氏名（和/英/ヨミ） | 入江 英嗣 / Hidetsugu Irie / イリエ ヒデツグ |
| 第3著者 所属（和/英） | 電気通信大学 (略称： 電通大) The University of Electro-Communications (略称： UEC) |
| 第4著者 氏名（和/英/ヨミ） | 吉永 努 / Tsutomu Yoshinaga / ヨシナガ ツトム |
| 第4著者 所属（和/英） | 電気通信大学 (略称： 電通大) The University of Electro-Communications (略称： UEC) |
| 講演者 | 第1著者 |
| 発表日時 | 2014-01-29 08:30:00 |
| 発表時間 | 25分 |
| 申込先研究会 | CPSY |
| 資料番号 | VLD2013-119, CPSY2013-90, RECONF2013-73 |
| 巻番号（vol） | vol.113 |
| 号番号（no） | no.416(VLD), no.417(CPSY), no.418(RECONF) |
| ページ範囲 | pp.103-108 |
| ページ数 | 6 |
| 発行日 | 2014-01-21 (VLD, CPSY, RECONF) |
[研究会発表申込システムのトップページに戻る]