著者

石川淑 田中飛鳥 宮崎敏明

雑誌

第74回全国大会講演論文集

巻号頁・発行日

vol.2012, no.1, pp.159-160, 2012-03-06

---

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の高速処理を目指してアルゴリズム全体のハードウェア化を検討したので報告する。