Smith-Watermanアルゴリズム向けビット並列手法の検討

• Item type: SIG Technical Reports(1)
• 公開日: 2014-01-21
• タイトル: Smith-Watermanアルゴリズム向けビット並列手法の検討
• タイトル / 言語: en
• タイトル: An Experimental Bit-Parallel Solution to Accelerate Smith-Waterman Algorithm
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 並列処理
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 電気通信大学大学院情報システム学研究科
• 著者所属: 電気通信大学大学院情報システム学研究科
• 著者所属: 電気通信大学大学院情報システム学研究科
• 著者所属: 電気通信大学大学院情報システム学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Systems, The University of Electro-Communications
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Systems, The University of Electro-Communications
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Systems, The University of Electro-Communications
• 著者所属(英): en
• 著者所属(英): Graduate School of Information Systems, The University of Electro-Communications
• 著者名: 須戸, 里織; 吉見, 真聡; 入江, 英嗣; 吉永, 努
• 著者名(英): Saori, Sudo; Masato, Yoshimi; Hidetsugu, IRIE; Tsutomu, Yoshinaga
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Smith-Waterman （SW） アルゴリズムは，2 つの文字列からよく一致する部分文字列を探索する計算手法であり，遺伝子やアミノ酸配列の配列類似性検索に広く応用されている．SW 法の高速化に関する様々な取り組みが行われているなかでも，演算効率を向上させるアルゴリズムの開発は，アクセラレータでの実行で大きな効果が期待できる．SW アルゴリズムと同様に動的計画法で計算を行う編集距離や最長共通部分列 （LCS） 問題では，アルゴリズムをビットベクトル同士の演算で実現するビット並列化が提案されており，並列度の大きな向上が報告されている．本研究報告では，SW アルゴリズムのピット並列化について議論する．パラメータに制約のある簡略版の SW 法を対象に，ブロック単位の入出力をビットベクトルで列挙し，入出力間の演算を進化的計算を用いて発見した得られた論理式を元に速度評価を行い，ピット並列 SW アルゴリズムの実現可能性について議論する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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 in put 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11451459
• 書誌情報: 研究報告システムLSI設計技術（SLDM）; 巻 2014-SLDM-164, 号 18, p. 1-6, 発行日 2014-01-21
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会