配列アライメント

参照 : GTCGTAGAATA 読み取り: CACGTAG—TA CIGAR: 2S5M2D2M ここで: 2S = 2 ソフト クリッピング (ミスマッチ、または一致したシーケンスより長い読み取りである可能性があります) 5M = 5 一致またはミスマッチ 2D = 2 欠失 2M = 2 一致またはミスマッチ

exonerateアライメントプログラムのオリジナルのCIGARフォーマットでは、M文字を含むミスマッチとマッチを区別していませんでした。

SAMv1仕様書では、より新しいCIGARコードが定義されています。ほとんどの場合、一致または不一致を示すために、曖昧な古い「M」文字ではなく、「=」と「X」文字を使用することが推奨されます。

• 「クエリを消費する」と「参照を消費する」は、CIGAR操作によってアライメントがそれぞれクエリ配列と参照配列に沿って進むかどうかを示します。
• Hは、最初または最後の演算としてのみ存在できます。
• Sは、CIGAR文字列の両端との間にH演算のみを行うことができる。
• mRNAとゲノムのアライメントにおいて、N演算はイントロンを表します。その他のタイプのアライメントでは、Nの解釈は定義されていません。
• M/I/S/=/X 演算の長さの合計は SEQ の長さと等しくなる。

特定のペアワイズアライメントの有用性を定量化する1つの方法は、「最大一意マッチ」（MUM）、つまり両方のクエリ配列に出現する最長のサブシーケンスです。MUMシーケンスが長いほど、計算生物学におけるゲノムの多重配列アライメントにおいて、より近縁であることを示します^{[ 9 ]}。MUMmerなどの大規模なアライメントシステムでは、MUMやその他の潜在的なアンカーの識別が最初のステップです。アンカーは、2つのゲノム間で非常に類似している領域です。MUMとは何かを理解するために、頭字語の各単語を分解してみましょう。マッチとは、アライメントする両方の配列にサブストリングが出現することを意味します。一意とは、各配列にサブストリングが1回だけ出現することを意味します。最後に、最大とは、サブストリングが、上記の2つの要件を満たす別のより大きな文字列の一部ではないことを意味します。この背後にある考え方は、完全に一致し、各ゲノムに1回だけ出現する長いシーケンスは、ほぼ確実にグローバルアライメントの一部であるということです。

より正確に言うと：

「2つのゲノムAとBが与えられたとき、最大一意一致（MUM）部分文字列は、指定された最小長d（デフォルトではd=20）よりも長い長さのAとBの共通部分文字列であり、

• それは最大であり、つまり、不一致を生じさせることなく両端に拡張することはできない。
• 両方の配列においてユニークである」^{[ 10 ]}

ドットマトリックス法は、個々の配列領域のアライメントのファミリーを暗黙的に生成するため、定性的で概念的に単純ですが、大規模な分析には時間がかかります。ノイズがない場合、ドットマトリックス図から挿入、欠失、繰り返し、逆方向繰り返しなどの特定の配列の特徴を視覚的に識別するのは容易です。ドットマトリックス図を作成するには、2 つの配列を 2 次元マトリックスの最上行と最左列に書き込み、適切な列の文字が一致する任意の場所にドットを配置します。これは典型的な再帰プロットです。保守的な置換に対応するために、2 つの文字の類似度に応じてドットのサイズまたは強度を変化させる実装もあります。非常に類似した配列のドットプロットは、マトリックスの主対角線に沿って 1 本の線として表示されます。

ドットプロットを情報表示手法として用いる場合の問題点としては、ノイズ、不明瞭さ、直感性の欠如、2つの配列におけるマッチの要約統計量やマッチ位置の抽出の難しさなどが挙げられます。また、マッチデータが対角線上に重複して表示されるため、無駄なスペースが多く、プロットの実際の領域の大部分が空白またはノイズで占められてしまいます。さらに、ドットプロットは2つの配列に限定されます。これらの制限はMiropeatsアライメント図には当てはまりませんが、Miropeatsアライメント図には独自の欠点があります。

ドットプロットは、単一の配列における反復性を評価するためにも使用できます。配列をそれ自身と比較すると、有意な類似性を持つ領域は主対角線から外れた線として表示されます。この効果は、タンパク質が複数の類似した構造ドメインから構成されている場合に発生します。

動的計画法の手法は、Needleman-Wunsch アルゴリズムによるグローバル アライメントと、Smith-Waterman アルゴリズムによるローカルアライメントの生成に適用できます。一般的な使用法では、タンパク質アライメントは置換行列を使用してアミノ酸の一致または不一致にスコアを割り当て、一方の配列のアミノ酸が他方の配列のギャップに一致する場合にギャップ ペナルティを割り当てます。DNA および RNA アライメントではスコアリング マトリックスを使用する場合があります。ただし、実際には、単に正の一致スコア、負の不一致スコア、および負のギャップ ペナルティを割り当てることがよくあります。（標準的な動的計画法では、各アミノ酸位置のスコアは隣接するアミノ酸の同一性とは無関係であるため、塩基スタッキング効果は考慮されません。ただし、アルゴリズムを修正することで、そのような効果を考慮することは可能です。） 標準的な線形ギャップ コストの一般的な拡張として、アフィン ギャップ コストがあります。ここでは、ギャップを開く場合とギャップを拡張する場合に 2 つの異なるギャップ ペナルティが適用されます。通常、前者は後者よりもはるかに大きく、たとえばギャップを開く場合は -10、ギャップを拡張する場合は -2 です。これにより、アライメントのギャップが少なくなり、残基とギャップが一緒に保持されるため、生物学的配列の特徴がよりよく表れる。Gotohアルゴリズムは、3つの行列を使用してアフィンギャップコストを実装する。^{[ 11 ] [ 12 ]}

動的計画法は、ヌクレオチド配列とタンパク質配列のアラインメントに役立ちます。この作業は、フレームシフト変異（通常は挿入または欠失）を考慮する必要があるため複雑です。フレームサーチ法は、クエリヌクレオチド配列と検索対象のタンパク質配列セットの間、またはその逆の、一連のグローバルまたはローカルなペアワイズアラインメントを生成します。任意の数のヌクレオチドでオフセットされたフレームシフトを評価できるため、この方法は、多数のインデルを含む配列に役立ちます。インデルは、より効率的なヒューリスティック法ではアラインメントが非常に困難な場合があります。実際には、この方法には大量の計算能力、または動的計画法に特化したアーキテクチャを持つシステムが必要です。BLASTおよびEMBOSSスイートは、翻訳されたアラインメントを作成するための基本的なツールを提供します（ただし、これらのアプローチの一部は、ツールの配列検索機能の副作用を利用しています）。より一般的な方法は、GeneWiseなどのオープンソースソフトウェアから入手できます。

動的計画法は、特定のスコアリング関数が与えられた場合、最適なアライメントを見つけることが保証されています。しかし、適切なスコアリング関数を特定することは、理論的な問題というよりは経験的な問題であることが多いです。動的計画法は2つ以上のシーケンスにも拡張可能ですが、シーケンスの数が非常に多い場合や、シーケンスが極めて長い場合は、処理速度が著しく低下します。

ワード法（ kタプル法とも呼ばれる）は、最適なアライメント解を見つけることが保証されていないものの、動的計画法よりもはるかに効率的なヒューリスティック法です。これらの方法は、候補配列の大部分がクエリ配列と実質的に有意な一致を示さないことがわかっている大規模なデータベース検索で特に役立ちます。ワード法は、データベース検索ツールFASTAおよびBLASTファミリーでの実装で最もよく知られています。^{[ 1 ]}ワード法は、クエリ配列内の短い重複しない部分配列（「ワード」）のシリーズを識別し、それらを候補データベース配列に一致させます。比較対象の2つの配列におけるワードの相対位置を減算してオフセットを取得します。複数の異なるワードが同じオフセットを生成する場合、これはアライメント領域を示します。この領域が検出された場合にのみ、これらの方法はより感度の高いアライメント基準を適用します。したがって、類似性がほとんどない配列との多くの不要な比較が排除されます。

FASTA 方式では、ユーザーがデータベースの検索に使用する単語長としてk の値を定義します。この方式は、 kの値が小さいほど検索速度は遅くなりますが感度が高く、非常に短いクエリ シーケンスを含む検索にも適しています。BLAST ファミリーの検索方式は、遠縁の配列の一致を検索するなど、特定のタイプのクエリに最適化された多数のアルゴリズムを提供します。BLAST は、精度を大きく損なうことなく FASTA よりも高速な代替手段を提供するために開発されました。FASTA と同様に、BLAST は長さkの単語検索を使用しますが、FASTA のようにすべての単語の一致を評価するのではなく、最も重要な単語の一致のみを評価します。ほとんどの BLAST 実装では、クエリとデータベースの種類に最適化された固定のデフォルトの単語長を使用し、反復的または非常に短いクエリ シーケンスで検索する場合など、特別な状況でのみ変更されます。実装は、EMBL FASTAやNCBI BLASTなどの多数の Web ポータルから入手できます。

動的計画法は理論的には任意の数のシーケンスに適用できますが、時間とメモリの両方で計算コストが高いため、最も基本的な形式では3つまたは4つ以上のシーケンスにはほとんど使用されません。この方法では、2つのシーケンスから形成されるシーケンス行列のn次元相当物を構築する必要があります。ここでnはクエリ内のシーケンスの数です。標準的な動的計画法は、まずすべてのクエリシーケンスのペアに適用され、次に中間位置での可能な一致またはギャップを考慮して「アライメント空間」が埋められ、最終的に各2つのシーケンスのアライメント間で本質的にアライメントが構築されます。この手法は計算コストが高いですが、グローバル最適解が保証されるため、少数のシーケンスのみを正確にアライメントする必要がある場合に役立ちます。動的計画法の計算要求を削減する1つの方法は、「ペアの合計」目的関数に依存しており、 MSA ^{[リンク削除]}ソフトウェアパッケージに実装されています。^{[ 15 ]}

プログレッシブ法、階層法、またはツリー法では、まず最も類似した配列をアラインメントし、次にクエリセット全体がソリューションに組み込まれるまで、関連性の低い配列またはグループを順次アラインメントに追加することで、多重配列アラインメントを生成します。配列の関連性を記述する初期ツリーは、FASTAと同様のヒューリスティックなペアワイズアラインメント法を含むペアワイズ比較に基づいています。プログレッシブアラインメントの結果は、「最も関連性の高い」配列の選択に依存するため、初期ペアワイズアラインメントの不正確さに敏感になる可能性があります。ほとんどのプログレッシブ多重配列アラインメント法では、クエリセット内の配列を関連性に応じて重み付けするため、初期配列の選択が不適切になる可能性が低くなり、アラインメントの精度が向上します。

Clustalのプログレッシブ実装^{[ 16 ] [ 17 ] [ 18 ]}の多くのバリエーションは、多重配列アライメント、系統樹の構築、およびタンパク質構造予測の入力として使用されています。プログレッシブメソッドのより遅いが正確なバリアントはT-Coffeeとして知られています。^{[ 19 ]}

反復法は、漸進法の弱点である初期ペアワイズアライメントの精度への過度な依存を改善しようと試みます。反復法は、選択されたアライメントスコアリング方法に基づいて目的関数を最適化し、初期グローバルアライメントを割り当て、次にシーケンスサブセットを再アライメントします。再アライメントされたサブセット自体がアライメントされ、次の反復の多重シーケンスアライメントが生成されます。シーケンスサブグループと目的関数を選択するさまざまな方法が^{[ 20 ]でレビューされています。}

プロファイル解析とも呼ばれるモチーフ探索では、クエリセット内の配列間で短い保存配列モチーフをアラインメントしようとするグローバル多重配列アラインメントを作成します。これは通常、まず一般的なグローバル多重配列アラインメントを作成し、次に高度に保存された領域を分離してプロファイル行列のセットを作成することによって行われます。各保存領域のプロファイル行列はスコアリング行列のように配置されますが、各位置における各アミノ酸またはヌクレオチドの頻度カウントは、より一般的な経験的分布からではなく、保存領域の特性分布から導出されます。次に、プロファイル行列を使用して、特徴付けられたモチーフの出現を他の配列で検索します。元のデータセットに少数の配列しか含まれていない場合、または高度に類似した配列のみが含まれている場合は、擬似カウントを追加して、モチーフで表された特性分布を正規化します。

コンピュータサイエンスで一般的に使用されているさまざまな汎用最適化アルゴリズムも、多重配列アライメント問題に適用されています。隠れマルコフモデルは、与えられたクエリセットの可能な多重配列アライメントのファミリーの確率スコアを生成するために使用されています。初期のHMMベースの方法は期待外れの性能でしたが、後のアプリケーションでは、保守的または半保守的な置換によって生成されるノイズの影響を受けにくいため、遠縁の配列を検出するのに特に効果的であることがわかりました。^{[ 21 ]}遺伝的アルゴリズムとシミュレーテッドアニーリングも、ペアの合計法などのスコアリング関数によって判断される多重配列アライメントスコアの最適化に使用されています。より詳細な情報とソフトウェアパッケージについては、メイン記事の多重配列アライメントを参照してください。

Burrows –Wheeler変換は、 BowtieやBWAなどの一般的なツールにおいて、高速ショートリードアライメントに成功裏に適用されています。FM -indexを参照してください。

DALI法、または距離行列アライメントは、クエリ配列内の連続するヘキサペプチド間の接触類似性パターンに基づいて構造アライメントを構築するフラグメントベースの方法です。^{[ 24 ]}この方法は、ペアワイズまたはマルチプルアライメントを生成し、 Protein Data Bank (PDB)内のクエリ配列の構造的近傍を特定できます。この方法は、 FSSP構造アライメントデータベース（タンパク質の構造-構造アライメントに基づくフォールド分類、または構造的に類似したタンパク質のファミリー）の構築に使用されています。DALIウェブサーバーはDALIでアクセスでき、FSSPはThe Dali Databaseにあります。

SSAP（sequential structure alignment program）は、構造空間内の原子間ベクトルを比較点として使用する動的計画法に基づく構造アライメント手法です。当初の説明以降、多重アライメントとペアワイズアライメントの両方を含むように拡張され^{[ 25 ]} 、タンパク質フォールドの階層的データベース分類であるCATH（Class、Architecture、Topology、Homology）の構築に使用されています^{[ 26 ]} 。CATHデータベースはCATH Protein Structure Classificationでアクセスできます。

構造アライメントの組み合わせ拡張法は、分析対象の 2 つのタンパク質の短い断片を局所的な幾何学を使用して整列させ、これらの断片をより大きなアライメントに組み立てることによって、ペアワイズ構造アライメントを生成します。^{[ 27 ]}剛体二乗平均平方根距離、残基間距離、局所二次構造、および残基近傍の疎水性などの周囲の環境特性などの尺度に基づいて、「整列された断片ペア」と呼ばれる局所アライメントが生成され、事前定義されたカットオフ基準内のすべての可能な構造アライメントを表す類似性マトリックスの構築に使用されます。次に、成長するアライメントを一度に 1 つの断片ずつ拡張することによって、マトリックスを通して、あるタンパク質構造状態から別のタンパク質構造状態へのパスがトレースされます。このような最適なパスが組み合わせ拡張アライメントを定義します。この方法を実装し、タンパク質データバンクの構造のペアワイズアライメントのデータベースを提供するウェブベースのサーバーは、組み合わせ拡張ウェブサイトにあります。

配列アライメントは、バイオインフォマティクスにおいて、配列類似性の特定、系統樹の作成、タンパク質構造の相同性モデルの開発に役立つ。しかし、配列アライメントの生物学的意義は必ずしも明確ではない。アライメントは、共通祖先から派生した配列間の進化的な変化の程度を反映していると想定されることが多いが、進化的に無関係でありながら類似した機能と構造を持つタンパク質間で、収斂進化によって見かけ上の類似性が生じる可能性も理論的には考えられる。

BLASTなどのデータベース検索では、統計的手法を用いて、検索対象のデータベースのサイズと構成に基づいて、配列間または配列領域間の特定のアライメントが偶然に生じる可能性を判定できます。これらの値は、検索空間によって大きく変動する可能性があります。特に、データベースがクエリ配列と同じ生物由来の配列のみで構成されている場合、特定のアライメントが偶然に見つかる可能性が高くなります。データベースまたはクエリ内の反復配列も、検索結果と統計的有意性の評価の両方を歪める可能性があります。BLASTは、統計的なアーティファクトである見かけ上のヒットを回避するために、クエリ内のこのような反復配列を自動的にフィルタリングします。

ギャップのある配列アライメントの統計的有意性推定法は文献で入手可能である。^{[ 28 ] [ 30 ] [ 31 ] [ 32 ] [ 33 ] [ 34 ] [ 35 ] [ 36 ]}

統計的有意性は、特定の品質のアライメントが偶然に生じる確率を示しますが、特定のアライメントが同じ配列の別のアライメントよりもどれだけ優れているかを示すものではありません。アライメントの信頼性の尺度は、特定の配列ペアに対する最もスコアの高いアライメントが実質的にどの程度類似しているかを示します。ギャップのある配列アライメントのアライメント信頼性推定方法は文献に記載されています。^{[ 37 ]}

既知の配列に関する生物学的または統計的観察を反映するスコアリング関数の選択は、良好なアライメントを作成する上で重要です。タンパク質配列は、特定の文字から文字への置換の確率を反映する置換行列を使用してアライメントされることがよくあります。PAM行列（Point Accepted Mutation matrices、元々はマーガレット・デイホフによって定義され、「デイホフ行列」と呼ばれることもある）と呼ばれる一連の行列は、特定のアミノ酸変異の速度と確率に関する進化的近似を明示的に符号化します。もう1つの一般的なスコアリング行列のシリーズであるBLOSUM（Blocks Substitution Matrix）は、経験的に導出された置換確率を符号化します。両方のタイプの行列のバリアントは、異なるレベルの分岐を持つ配列を検出するために使用され、BLASTまたはFASTAのユーザーが検索をより近縁の一致に限定したり、より分岐した配列を検出するように拡張したりすることを可能にします。ギャップペナルティは、ヌクレオチド配列とタンパク質配列の両方におけるギャップの導入（進化モデルでは挿入または欠失変異に相当）を考慮に入れるため、ペナルティ値はそのような変異の予想発生率に比例するべきである。したがって、生成されるアライメントの品質は、スコアリング関数の品質に依存する。

スコアリングマトリックスやギャップペナルティ値など、異なる選択肢を用いて同じアライメントを複数回試行し、結果を比較することは、非常に有益で参考になります。アライメントパラメータの変動に対してどの領域が頑健であるかを観察することで、解が弱い、あるいは一意でない領域を特定できる場合が多くあります。