BLASTアルゴリズムのハードウェア化の検討

概要

論文の詳細を見る
Basic Local Alignment Search Tool (BLAST)は最も有名なシーケンスアライメントツールの一つである。シーケンスアライメントとはタンパク質(またはDNA)データベースから検索対象となるタンパク質(またはDNA)配列を列挙することであり、配列同士の類似部分検索のために使用される。シーケンスアライメントは、生物学上の進化や遺伝子系図を調べる上で重要であることから、バイオインフォマティクス分野では欠かせない情報である。BLASTは、seeding(ステップ1)、ungapped extension(ステップ2)、gapped extension(ステップ3)という3つの処理ステップからなる。ステップ3のgapped extensionではSmith-Waterman アルゴリズムというDP(Dynamic Programming)が使用されており、従来ハードウェアによる多くの高速化手法が提案されている。しかし、BLAST全体をハードウェア化することは行われていない。本稿では、BLASTの高速処理を目指してアルゴリズム全体のハードウェア化を検討したので報告する。
一般社団法人情報処理学会の論文
2012-03-06