バイオインフォマティクス において、シーケンスアラインメント とは、DNA やRNA 、タンパク質 の配列 （一次構造 ）の類似した領域を特定できるように並べたもので、機能的、構造的、あるいは進化的な配列の関係性を知る手がかりを与える。配列アラインメント[ 1] [ 2]
アラインメントされたヌクレオチド 残基やアミノ酸 残基の配列は、典型的には行列の行として表現され、同一あるいは類似性質の配列が同じ列に並ぶようギャップが挿入される。
ClustalW による、GenBank から得た2つのヒト ジンクフィンガー タンパク質のシーケンスアラインメント アラインメントの二配列が祖先を共有する場合、分岐後の一方または両方の系統において、不一致部分は点変異 が、ギャップ部分はインデル （indel=挿入欠失; 挿入変異または欠失変異）が生じたものと解釈される。タンパク質の配列アラインメントでは、特定位置におけるアミノ酸の類似度は特定領域、あるいは配列モチーフが系統間でどのくらい保存されているかを示す大まかな目安と解釈できる。置換がないか、保守的置換（類似の生化学的特性を持った側鎖との置換）しかないとき、その領域は構造的、あるいは機能的に重要であると示唆される。DNAとRNAの塩基は、アミノ酸の場合よりも互いに類似しているものの、塩基対の保存は、構造的、機能的重要性を示唆している。シーケンスアラインメントは、自然言語 や金融データなどの非生物配列にも用いられる。
アラインメントはグラフィカルで表現されることも、テキストフォーマットでも表現されることもある。多くのシーケンスアラインメント表現において、各配列は類似残基が同列にならぶように並べられる。
グローバルアラインメントとローカルアラインメントの違いを表す図。配列が十分に似ていない場合、グローバルアラインメントではギャップが多くなる。 グローバルアラインメントとは配列中の全残基がアラインメントされるようにしたもので、ほぼ同じ長さの配列間での比較に有効である。
ローカルアラインメントは、配列が全体としては似ておらず、部分的類似を見つけたい場合に有効である。
ペアワイズシーケンスアラインメントは、2配列間でのアラインメントで、部分的、あるいは全体の類似性を詳しく調べるときに用いる。
ヒト ジンクフィンガー 転写因子 (GenBank ID NM_002383)のDNAのドットプロット。 遺伝子の配列内部の部分的な相同性を示している。図左上から右下に至る対角線は配列それ自身同士のアライメントを示しており、 それ以外の線は相同性や反復的な配列のパターンを示している。 これはrecurrence plot の典型的な例の1つである。 ドットマトリックス的な手法では、結果として得られるアライメントは各配列内の領域間のアライメントで、多数のアライメントが得られる。
考え方としてはシンプルだが、大規模な計算になると時間を要する。ノイズさえなければ、配列間の相同性の点から見て特徴的な領域を
目視で容易に判別できる。
例えば挿入や、欠失、反復配列、Inverted repeatなどは、二次元ドットマトリックスのプロットから見つけられる。
ドットマトリックスプロットを作図するには、まず二次元の行列の行に片方に一本の配列を割当て、列にもう一本の配列を割り当てる。そして性質の一致する行と列の交差する箇所に点を描画していく。ドットプロットの実装によっては類似性の程度をドットのサイズや濃さで表すものもある。
動的計画法 （英語 : dynamic programming ）の代表的な手法として、グローバルアラインメントについては Needleman-Wunsch法(ニードルマン＝ウンシュ法)、ローカルアライメントについてはSmith-Waterman法(スミス＝ウォーターマン法)がある。例えばタンパク質のアライメントでは、アミノ酸の一致・不一致に対しして置換マトリックスを参照してスコアを付与し、ギャップにはペナルティを付与するような計算である。
ワード法は、k-tuple法としても知られるヒューリスティック な方法で、最適アラインメントが見つかることを保証しないが、ダイナミックプログラミングよりも遙かに効率が良い。このため、大規模なデータベース検索に多く用いられる。この方法はFASTA やBLAST といったアラインメントツールが用いていることで知られている。
ワード法では、まずクエリ配列を短い部分配列（ワード）に分け、その中からデータベースの配列に合うものを見つける。見つかったワードについて、比較対象の2配列中の相対位置を抽出し、オフセットを得る。もし複数のワードを用いて同じオフセットが得られれば、アラインメントすべき領域が示されたことになる。そのような領域が見つかった場合にのみ、より感度の高いアラインメントが適応される。これによって、明らかに似ていない配列間の不要な比較を減らすことができる。
27本の鳥インフルエンザ ヘマグルチニン の配列のアラインメントの、残基の保存性（上）と残基の性質（下）による色分け 多重配列アライメント（マルチプルアラインメント、英語 : multiple alignment ）は3配列以上を扱うペアワイズアラインメントの拡張で、進化的に保存された配列の同定などに用いられる。多重アライメント方式は与えられたシーケンス全てに対してアライメントを試みる。多重アライメントはよく、進化に関係するという仮説のグループが交わる保存配列 領域の決定に用いられる。このような保存配列 のモチーフ は酵素 の触媒の活性サイト を位置づける構造と反応機構 の情報の組み合わせに用いられる。アライメントは系統樹 を組み立てることで進化の関係を立証するのを助けるのにも用いられる。
多重配列アライメントはコンピュータ処理的にNP完全 な組合せ最適化問題 につながる問題の定式化や生成が難しい[ 3] [ 4]
動的計画法 は、理論的にはいくつのシーケンスに対しても適用可能である。しかし、n次の時間とメモリ空間を要するため、3配列以上の場合にはそのまま適用されることはほとんどない。標準の動的計画法ではまずすべてのクエリのペアが使用され、アライメントスペース（英 : alignment space ）を中間的な位置の可能なマッチやギャップを考慮して満たす。やがて2つのシーケンスアライメントの間の基本的なアライメントが構成される。この方式は計算コストが高いが、その全体的な最適解の保証は少数のシーケンスを正確に配置する必要があるときに有用である。
動的計画法の計算コストを減らすためのひとつの方式はそれは「ペアの総計」の最適化関数を信頼するものだが、ソフトウェアパッケージのMSA で実装されている[ 5]
プログレッシブ法、階層法、ツリー法は、最も似ている配列同士を最初にアラインメントし、順次配列を加えてゆくことによって多重整列を構成する方法で、Clustal の多くの版[ 6] [ 7] [ 8] [ 9] タンパク質構造予測 に用いられる。
繰り返し法は、プログレッシブ法の弱点を補うための方法で、繰り返し最適化を行う。[ 10]
モチーフ検索（プロファイル解析とも）はクエリセット内のシーケンスから短い保護モチーフ配列 を配置することを試みるような全域的な多重配列アラインメントを構成する。これはだいたいまず一般の多重配列アラインメント全体を構成し、その後高次の保存配列 が分離され、プロファイル行列セットを組み立てることで行われる。保存領域のプロファイル配列はスコアリング行列のように配置されるが、大量のアミノ酸やヌクレオチドそれぞれの位置は保存された領域の文字分布というよりももっと一般的な経験的な分布に由来する。プロファイル行列はそれらを文字列化するモチーフの発生のためのその他のシーケンスの検索にも用いられる。元のデータセットが少数のシーケンスを含んでいるまたは高次の関係シーケンスのみであった場合、擬似カウント （英語版 ）
コンピュータサイエンスにおける一般的な最適化 アルゴリズムには多重配列アラインメントの問題が適用される。
隠れマルコフモデル は与えられたクエリセットに対して多重配列アライメント群の確率点を生成するのに用いられるが、
初期の隠れマルコフモデルをもとにした方式はとても遅く、後のアプリケーションは特に効果的なもの、保守的または半保存的な置換を行うときに生成されるノイズの影響を受けにくいような関係が薄いシーケンスを検出するようになった。[ 11] 遺伝的アルゴリズム や焼きなまし法 は同様にsum of pairsメソッドのようなスコアリング関数によって判定される多重配列アラインメントのスコアの最適化に用いられる。
Burrows–Wheeler変換 はFM-index （英語版 ）
構造アラインメントは、通常タンパク質の二次構造と三次構造の情報を用いて、配列アラインメントを構築するものだが、RNAに用いられることもある。タンパク質においては挿入や欠損は多くの場合ランダムコイルやループ上で起こる。構造アラインメントは配列アラインメントを実施したのちに、挿入や欠損配列をランダムコイルやループ上で起こるように再アラインすることを指す。
選択的スプライシング で用いられる。
^ 阿久津 達也 (2019年). “生命情報学（２）配列解析基礎 ”. 京都大学 化学研究所 バイオインフォマティクスセンター. 2024年12月22日 閲覧。 ^ “配列アライメント ”. ライフサイエンスデータベースアーカイブ . DBCLS. 2024年12月22日 閲覧。 ^ Wang L, Jiang T. (1994). “On the complexity of multiple sequence alignment” . J Comput Biol 1 (4): 337–48. doi :10.1089/cmb.1994.1.337 . PMID 8790475 . http://www.liebertonline.com/doi/abs/10.1089/cmb.1994.1.337 . ^ Elias, Isaac (2006). “Settling the intractability of multiple alignment” . J Comput Biol 13 (7): 1323–1339. doi :10.1089/cmb.2006.13.1323 . PMID 17037961 . http://www.liebertonline.com/doi/abs/10.1089/cmb.2006.13.1323 . ^ Lipman DJ, Altschul SF, Kececioglu JD (1989). “A tool for multiple sequence alignment” . Proc Natl Acad Sci USA 86 (12): 4412–5. doi :10.1073/pnas.86.12.4412 . PMC 287279 . PMID 2734293 . http://www.pnas.org/cgi/pmidlookup?view=long&pmid=2734293 . ^ Higgins DG, Sharp PM (1988). “CLUSTAL: a package for performing multiple sequence alignment on a microcomputer” . Gene 73 (1): 237–44. doi :10.1016/0378-1119(88)90330-7 . PMID 3243435 . http://linkinghub.elsevier.com/retrieve/pii/0378-1119(88)90330-7 . ^ Thompson JD, Higgins DG, Gibson TJ. (1994). “CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice” . Nucleic Acids Res 22 (22): 4673–80. doi :10.1093/nar/22.22.4673 . PMC 308517 . PMID 7984417 . http://nar.oxfordjournals.org/content/22/22/4673 . ^ Chenna R, Sugawara H, Koike T, Lopez R, Gibson TJ, Higgins DG, Thompson JD. (2003). “Multiple sequence alignment with the Clustal series of programs” . Nucleic Acids Res 31 (13): 3497–500. doi :10.1093/nar/gkg500 . PMC 168907 . PMID 12824352 . http://nar.oxfordjournals.org/cgi/pmidlookup?view=long&pmid=12824352 . ^ Notredame C, Higgins DG, Heringa J. (2000). “T-Coffee: A novel method for fast and accurate multiple sequence alignment” . J Mol Biol 302 (1): 205–17. doi :10.1006/jmbi.2000.4042 . PMID 10964570 . http://linkinghub.elsevier.com/retrieve/pii/S0022-2836(00)94042-7 . ^ Hirosawa M, Totoki Y, Hoshida M, Ishikawa M. (1995). “Comprehensive study on iterative algorithms of multiple sequence alignment” . Comput Appl Biosci 11 (1): 13–8. doi :10.1093/bioinformatics/11.1.13 . PMID 7796270 . http://bioinformatics.oxfordjournals.org/cgi/content/abstract/11/1/13 . ^ Karplus K, Barrett C, Hughey R. (1998). “Hidden Markov models for detecting remote protein homologies” . Bioinformatics 14 (10): 846–856. doi :10.1093/bioinformatics/14.10.846 . PMID 9927713 . http://bioinformatics.oxfordjournals.org/cgi/pmidlookup?view=long&pmid=9927713 .
![[icon]](%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB:Wiki_letter_w_cropped.svg){kind=small}
