バイオインフォマティクスにおいて、シーケンスアラインメントとは、DNAやRNA、タンパク質の配列（一次構造）の類似した領域を特定できるように並べたもので、機能的、構造的、あるいは進化的な配列の関係性を知る手がかりを与える。
アラインメントされたヌクレオチド残基やアミノ酸残基の配列は、典型的には行列の行として表現され、同一あるいは類似性質の配列が同じ列に並ぶようギャップが挿入される。
アラインメントの二配列が祖先を共有する場合、分岐後の一方または両方の系統において、不一致部分は点変異が、ギャップ部分はインデル（indel=挿入欠失; 挿入変異または欠失変異）が生じたものと解釈される。タンパク質の配列アラインメントでは、特定位置におけるアミノ酸の類似度は特定領域、あるいは配列モチーフが系統間でどのくらい保存されているかを示す大まかな目安と解釈できる。置換がないか、保守的置換（類似の生化学的特性を持った側鎖との置換）しかないとき、その領域は構造的、あるいは機能的に重要であると示唆される。DNAとRNAの塩基は、アミノ酸の場合よりも互いに類似しているものの、塩基対の保存は、構造的、機能的重要性を示唆している。シーケンスアラインメントは、自然言語や金融データなどの非生物配列にも用いられる。
表現
アラインメントはグラフィカルで表現されることも、テキストフォーマットでも表現されることもある。多くのシーケンスアラインメント表現において、各配列は類似残基が同列にならぶように並べられる。
グローバルアラインメントとローカルアラインメント
グローバルアラインメントとは配列中の全残基がアラインメントされるようにしたもので、ほぼ同じ長さの配列間での比較に有効である。 ローカルアラインメントは、配列が全体としては似ておらず、部分的類似を見つけたい場合に有効である。
ペアワイズアラインメント
ペアワイズシーケンスアラインメントは、2配列間でのアラインメントで、部分的、あるいは全体の類似性を詳しく調べるときに用いる。
ドットマトリクス法
ドットマトリックス的な手法では、結果として得られるアライメントは各配列内の領域間のアライメントで、多数のアライメントが得られる。 考え方としてはシンプルだが、大規模な計算になると時間を要する。ノイズさえなければ、配列間の相同性の点から見て特徴的な領域を 目視で容易に判別できる。 例えば挿入や、欠失、反復配列、Inverted repeatなどは、二次元ドットマトリックスのプロットから見つけられる。
ドットマトリックスプロットを作図するには、まず二次元の行列の行に片方に一本の配列を割当て、列にもう一本の配列を割り当てる。そして性質の一致する行と列の交差する箇所に点を描画していく。ドットプロットの実装によっては類似性の程度をドットのサイズや濃さで表すものもある。
動的計画法
動的計画法（英語: dynamic programming）の代表的な手法として、グローバルアラインメントについては Needleman-Wunsch法(ニードルマン＝ウンシュ法)、ローカルアライメントについてはSmith-Waterman法(スミス＝ウォーターマン法)がある。例えばタンパク質のアライメントでは、アミノ酸の一致・不一致に対しして置換マトリックスを参照してスコアを付与し、ギャップにはペナルティを付与するような計算である。
ワード法
ワード法は、k-tuple法としても知られるヒューリスティックな方法で、最適アラインメントが見つかることを保証しないが、ダイナミックプログラミングよりも遙かに効率が良い。このため、大規模なデータベース検索に多く用いられる。この方法はFASTAやBLASTといったアラインメントツールが用いていることで知られている。
ワード法では、まずクエリ配列を短い部分配列（ワード）に分け、その中からデータベースの配列に合うものを見つける。見つかったワードについて、比較対象の2配列中の相対位置を抽出し、オフセットを得る。もし複数のワードを用いて同じオフセットが得られれば、アラインメントすべき領域が示されたことになる。そのような領域が見つかった場合にのみ、より感度の高いアラインメントが適応される。これによって、明らかに似ていない配列間の不要な比較を減らすことができる。
多重配列アライメント
 |
この項目「シーケンスアラインメント」は翻訳されたばかりのものです。不自然あるいは曖昧な表現などが含まれる可能性があり、このままでは読みづらいかもしれません。（原文：英語版 "Sequence alignment" 2013-6-11 13:16 (UTC)） 修正、加筆に協力し、現在の表現をより自然な表現にして下さる方を求めています。ノートページや履歴も参照してください。（2013年6月） |
多重配列アライメント（マルチプルアラインメント、英語: multiple alignment）は3配列以上を扱うペアワイズアラインメントの拡張で、進化的に保存された配列の同定などに用いられる。多重アライメント方式は与えられたシーケンス全てに対してアライメントを試みる。多重アライメントはよく、進化に関係するという仮説のグループが交わる保存配列領域の決定に用いられる。このような保存配列のモチーフは酵素の触媒の活性サイトを位置づける構造と反応機構の情報の組み合わせに用いられる。アライメントは系統樹を組み立てることで進化の関係を立証するのを助けるのにも用いられる。 多重配列アライメントはコンピュータ処理的にNP完全な組合せ最適化問題につながる問題の定式化や生成が難しい。それでもバイオインフォマティクスにおいてこれらのアライメントのユーティリティは3つ以上のアライメントに対する適切な方式の種類の開発に役立つ。
動的計画法
動的計画法は、理論的にはいくつのシーケンスに対しても適用可能である。しかし、n次の時間とメモリ空間を要するため、3配列以上の場合にはそのまま適用されることはほとんどない。標準の動的計画法ではまずすべてのクエリのペアが使用され、アライメントスペース（英: alignment space）を中間的な位置の可能なマッチやギャップを考慮して満たす。やがて2つのシーケンスアライメントの間の基本的なアライメントが構成される。この方式は計算コストが高いが、その全体的な最適解の保証は少数のシーケンスを正確に配置する必要があるときに有用である。 動的計画法の計算コストを減らすためのひとつの方式はそれは「ペアの総計」の最適化関数を信頼するものだが、ソフトウェアパッケージのMSAで実装されている。
プログレッシブ法、階層法、ツリー法
プログレッシブ法、階層法、ツリー法は、最も似ている配列同士を最初にアラインメントし、順次配列を加えてゆくことによって多重整列を構成する方法で、Clustalの多くの版や、T-Coffeeなどがある。タンパク質構造予測に用いられる。
繰り返し法
繰り返し法は、プログレッシブ法の弱点を補うための方法で、繰り返し最適化を行う。
モチーフ検索
モチーフ検索（プロファイル解析とも）はクエリセット内のシーケンスから短い保護モチーフ配列を配置することを試みるような全域的な多重配列アラインメントを構成する。これはだいたいまず一般の多重配列アラインメント全体を構成し、その後高次の保存配列が分離され、プロファイル行列セットを組み立てることで行われる。保存領域のプロファイル配列はスコアリング行列のように配置されるが、大量のアミノ酸やヌクレオチドそれぞれの位置は保存された領域の文字分布というよりももっと一般的な経験的な分布に由来する。プロファイル行列はそれらを文字列化するモチーフの発生のためのその他のシーケンスの検索にも用いられる。元のデータセットが少数のシーケンスを含んでいるまたは高次の関係シーケンスのみであった場合、擬似カウントはモチーフを表す正規化された文字列分布が追加される。
計算機科学による方法
コンピュータサイエンスにおける一般的な最適化アルゴリズムには多重配列アラインメントの問題が適用される。 隠れマルコフモデルは与えられたクエリセットに対して多重配列アライメント群の確率点を生成するのに用いられるが、 初期の隠れマルコフモデルをもとにした方式はとても遅く、後のアプリケーションは特に効果的なもの、保守的または半保存的な置換を行うときに生成されるノイズの影響を受けにくいような関係が薄いシーケンスを検出するようになった。遺伝的アルゴリズムや焼きなまし法は同様にsum of pairsメソッドのようなスコアリング関数によって判定される多重配列アラインメントのスコアの最適化に用いられる。
Burrows–Wheeler変換はFM-indexとしてBowtieやBWAのような一般的なツールの高速な短い読み込みアライメントに用いられる。
構造アラインメント
構造アラインメントは、通常タンパク質の二次構造と三次構造の情報を用いて、配列アラインメントを構築するものだが、RNAに用いられることもある。タンパク質においては挿入や欠損は多くの場合ランダムコイルやループ上で起こる。構造アラインメントは配列アラインメントを実施したのちに、挿入や欠損配列をランダムコイルやループ上で起こるように再アラインすることを指す。
![[icon]](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/20px-Wiki_letter_w_cropped.svg.png){kind=small} |
この節の加筆が望まれています。 |
系統樹解析
|
この節の加筆が望まれています。 |
生物学でのその他の用途
選択的スプライシングで用いられる。
その他の分野での利用
- 自然言語処理では、ニードルマン-ブンシュ・アルゴリズムとして用いられる。
- 言語学では最適マッチング法として用いられる。