シーケンスアラインメント
ワード法は、k-tuple法としても知られるヒューリスティックな方法で、最適アラインメントが見つかることを保証しないが、ダイナミックプログラミングよりも遙かに効率が良い。このため、大規模なデータベース検索に多く用いられる。この方法はFASTAやBLASTといったアラインメントツールが用いていることで知られている。
ワード法では、まずクエリ配列を短い部分配列(ワード)に分け、その中からデータベースの配列に合うものを見つける。見つかったワードについて、比較対象の2配列中の相対位置を抽出し、オフセットを得る。もし複数のワードを用いて同じオフセットが得られれば、アラインメントすべき領域が示されたことになる。そのような領域が見つかった場合にのみ、より感度の高いアラインメントが適応される。これによって、明らかに似ていない配列間の不要な比較を減らすことができる。