ホモロジー検索プログラムFLASHの改良について

概要

論文の詳細を見る
遺伝子(DNA)も蛋白も3次元構造を無視すれば共に文字列としてモデル化できる。1993年の時点で主要な遺伝子データベース(DDBJ、GenBank、EMBL)はすでに1億塩基対を越え、2年ごとに倍に増えている。医療、薬品、食品、農業など広範囲の産業への応用のためにも、この大量データへの高速で高感度の検索技術が必要となっている。現在、最も基本となる検索の仕方は、ユーザの指定した参照配列に類似した配列を含む遺伝子や蛋白を取り出す類似検索(ホモロジー検索)である。類似検索の実現手法には、(1)データベース全体を毎回サーチするダイナミック・プログラミングの手法(BLAZEやジFASTAなど)と(2)検索インデックスを事前に作成しそれを用いて検索する手法(BLASTやFASTAなど)とがある。後者は検出速度が速いが、検出感度や柔軟性の点で劣ると考えられてきた。これに対し、Califanoらは検出速度と検出感度が共に高い手法として多重インデックスに基づく手法(FLASH)を最近提唱した。ここでは、このアルゴリズムについて簡単に述べた後、その改良として、挿入/消除における感度の向上と局所的類似検索への拡張を述べる。
一般社団法人情報処理学会の論文
1994-03-07