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

摘要

Smith-Waterman（SW）アルゴリズムは，2つの文字列からよく一致する部分文字列を探索する計算手法であり，遺伝子やアミノ酸配列の配列類似性検索に広く応用されている．SW法の高速化に関する様々な取り組みが行われているなかでも，演算効率を向上させるアルゴリズムの開発は，アクセラレータでの実行で大きな効果が期待できる．SWアルゴリズムと同様に動的計画法で計算を行う編集距離や最長共通部分列（LCS）問題では，アルゴリズムをビットベクトル同士の演算で実現するビット並列化が提案されており，並列度の大きな向上が報告されている．本研究報告では，SWアルゴリズムのビット並列化について議論する．パラメータに制約のある簡略版のSW法を対象に，ブロック単位の入出力をビットベクトルで列挙し，入出力間の演算を進化的計算を用いて発見した．得られた論理式を元に速度評価を行い，ビット並列SWアルゴリズムの実現可能性について議論する．