FPGAを用いたHMMERの高速化

摘要

本論文ではFPGAを用いたHMMERの高速化手法について述べる．HMMERはプロファイルHMMを用いたタンパク質配列検索プログラムである.プロファイルHMMではモデルの最後から最初へのフィードバック経路が許されており,この経路がHMMERで用いられているビタビアルゴリズムの並列計算を難しくしている．我々の手法では投機的な並列処理を行い,結果的にフィードバック経路が選択された場合にはフィードバックスコアを用い再計算を行う.FPGAを用いたHMMERの高速化における他の問題点は，プロファイルHMMに必要となるスコアテーブルの大きさである.二次元探索空間における探索方向とそれぞれの計算回路の走査方向を直行させることにより,スコアテーブル用のメモリー量を最小化することができる．この最適化によりデータベース中のすべてのプロファイルHMMを計算することが可能になる．%This paper describes an implementation of HMMER with FPGA. HMMER is one of the most used software tools for sensitive profile HMM searches of biological sequence databases. In the profile HMM, a feedback path from the end of the model to the beginning is allowed, and this loop makes it difficult to process the Viterbi algorithm in parallel. In our approach, the alignment is calculated speculatively in parallel, and when the feedback path is selected in the alignment, the alignment is recalculated from the beginning using the fedback score. Another problem for accelerating HMMER using FPGA is the large size of the score tables required for profile HMMs. By crossing the search direction in the quadratic search space and the moving direction of each processing unit in the search space, we can minimize the size of the memory banks for storing the score tables.