BLASTアルゴリズム

ウィキペディア小見出し辞書

BLASTアルゴリズム

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/11 08:28 UTC 版)

「BLAST」の記事における「BLASTアルゴリズム」の解説

BLASTアルゴリズムを実行する際には、2つの情報が必要である。クエリシーケンス（ターゲットシーケンスともいう）とシーケンスデータベースである。BLASTアルゴリズムは、シーケンスデータベース中のシーケンス断片と類似するクエリシーケンス中のシーケンス断片を見つけ出す。多くの場合、クエリシーケンスは、シーケンスデータベースと比べてデータ量が非常に小さい。例えば、クエリシーケンスが千個程度のヌクレオチド（核酸塩基）であるのに対し、シーケンスデータベースは数億のヌクレオチドのデータをもっている場合がある。 BLASTアルゴリズムは、クエリシーケンスとシーケンスデータベースとの間で、高い閾値でシーケンスアライメントを行う。その際には Smith-Waterman アルゴリズムに近似したヒューリスティクなアルゴリズムが使われる。完全な Smith-Waterman アルゴリズムは、NCBI GenBank のような大規模なシーケンスデータベースに対して検索を行う場合には、処理速度が非常に遅いことが問題となる。BLASTアルゴリズムは、Smith-Waterman アルゴリズムより少し正確さで劣るが、50倍以上の処理速度を実現する。このようにBLASTアルゴリズムは、高速でありかつ比較的正確であるという特徴がある。こうした特徴が、BLASTアルゴリズムの重要な技術的革新性であり、またおそらくバイオインフォマティクスにおいてBLASTプログラムが最もよく使われている理由となっている。 BLASTアルゴリズムの実行は、概念的には次に述べるように3段階に分かれている。 第1段階: クエリシーケンスを短い固定長データに分割した断片で、シーケンスデータベースを厳密に検索する。この固定長データの長さを W（ワード）とする。例えば、W = 3 で、クエリシーケンス AGTTAC に対してデータベース中に ACTTAG というシーケンスが存在した場合、BLASTアルゴリズムは、TTA という部分データが両シーケンスで共有されていると認識する。W のサイズは、特に指定しない場合、ヌクレオチドでは11、アミノ酸では3である。 第2段階: BLASTアルゴリズムは、クエリシーケンスと、部分データを共有すると認識したデータベース中のシーケンス群に対して、ギャップを考慮しない単純なアライメントを行う。このギャップを考慮しないアライメントは、第1段階の W の長さの固定長での検索処理を、アライメントのスコアが高くなるように両方向に W（ワード）のサイズを拡張した処理である。この段階ではヌクレオチド（核酸塩基）やアミノ酸の挿入や欠損は考慮しない。先述の例では、AGTTAC と ACTTAG はそれぞれ TTA を共に含んでおり、ギャップを考慮しないアライメントは次のようになる。..AGTTAC.. | ||| ..ACTTAG.. 第2段階で、ギャップを考慮せずに、スコアの高いアライメントが行えた場合、データベースのシーケンスデータは第3段階の処理対象となる。 第3段階: BLASTアルゴリズムは、Smith-Waterman アルゴリズムの変形版アルゴリズムで、クエリシーケンスとデータベースのシーケンスの間で、ギャップを考慮したアライメントを行う。アライメントを行った後、統計的に有意なアライメント群がユーザに示される。 BLASTから派生したアルゴリズムがいくつか考案されている。 BLAT BLAT (Blast Like Alignment Tool) は、BLASTを上回る速度で処理を行うが、正確さにおいてはBLASTに劣る。ヌクレオチドのシーケンスでゲノムデータベースへの検索を行う。 BLASTZ 複数の大規模なゲノムデータベースや染色体データベースに対して検索を行うよう設計されたアルゴリズム。