配列アライメント

バイオインフォマティクスにおいて、配列アライメントとは、 DNA、RNA、またはタンパク質の配列を配列し、配列間の機能的、構造的、または進化的関係の結果である可能性のある類似領域を識別する方法です。 ^[1]ヌクレオチドまたはアミノ酸残基のアライメントされた配列は、通常、マトリックス内の行として表されます。残基間にギャップが挿入されるため、同一または類似の文字は連続する列に揃えられます。配列アライメントは、自然言語の文字列間の距離コストの計算や、財務データの表示など、非生物学的配列にも使用されます。

アラインメント内の 2 つの配列が共通の祖先を共有する場合、ミスマッチは点突然変異として解釈でき、ギャップは、互いに分岐してからの期間に一方または両方の系統で導入されたインデル(つまり、挿入または欠失突然変異)として解釈できます。タンパク質の配列アラインメントでは、配列内の特定の位置を占めるアミノ酸間の類似性の程度は、特定の領域または配列モチーフが系統間でどれだけ保存されているかの大まかな尺度として解釈できます。配列の特定の領域に置換がないか、非常に保守的な置換 (つまり、側鎖の生化学的特性が類似するアミノ酸の置換) のみが存在する場合は、この領域が構造的または機能的に重要であることが示唆されます^{[3] 。DNA および RNA}ヌクレオチド塩基はアミノ酸よりも互いに類似していますが、塩基対の保存性は同様の機能的または構造的役割を示している可能性があります。

非常に短い、または非常に類似した配列は、手作業でアラインメントできます。しかし、最も興味深い問題の多くは、人間の努力だけではアラインメントできない、長くて非常に変化に富んだ、または非常に多数の配列のアラインメントを必要とします。その代わりに、人間の知識は、高品質の配列アラインメントを生成するアルゴリズムの構築に適用され、時にはアルゴリズムで表現するのが難しいパターンを反映するように最終結果を調整するのに適用されます (特にヌクレオチド配列の場合)。配列アラインメントの計算アプローチは、一般的に、グローバル アラインメントとローカル アラインメントの 2 つのカテゴリに分類されます。グローバル アラインメントの計算は、アラインメントがすべてのクエリ配列の全長に及ぶように「強制」するグローバル最適化の一形態です。対照的に、ローカル アラインメントは、全体的に大きく異なることが多い長い配列内の類似領域を特定します。ローカル アラインメントは多くの場合好ましいですが、類似領域を特定するという追加の課題があるため、計算がより困難になる可能性があります。^{[4]さまざまな計算アルゴリズムが配列アラインメント問題に適用されています。これには、}動的プログラミングなどの遅いが形式的に正しい方法が含まれます。これらには、大規模なデータベース検索用に設計された効率的なヒューリスティック アルゴリズムや確率的手法も含まれますが、最適な一致が見つかることを保証するものではありません。

アラインメントは、通常、グラフィカル形式とテキスト形式の両方で表現されます。ほとんどすべての配列アラインメント表現では、配列は行に記述され、アラインメントされた残基が連続する列に表示されるように配置されます。テキスト形式では、同一または類似の文字を含むアラインメントされた列は、保存記号のシステムで示されます。上の画像のように、2 つの列間の同一性を示すためにアスタリスクまたはパイプ記号が使用されます。その他のあまり一般的ではない記号には、保存的置換を表すコロンと半保存的置換を表すピリオドがあります。多くの配列視覚化プログラムでは、個々の配列要素の特性に関する情報を表示するために色も使用されます。DNA および RNA 配列では、これは各ヌクレオチドに独自の色を割り当てることと同じです。上の画像のようなタンパク質アラインメントでは、特定のアミノ酸置換の保存性を判断するのに役立つように、色を使用してアミノ酸の特性を示すことがよくあります。複数の配列の場合、各列の最後の行は、アラインメントによって決定されたコンセンサス配列であることがよくあります。コンセンサス配列は、各ヌクレオチドまたはアミノ酸の文字のサイズが保存の程度に対応する配列ロゴを使用してグラフィカル形式で表現されることもよくあります。^[5]

配列アライメントは、さまざまなテキストベースのファイル形式で保存できます。その多くは、もともと特定のアライメントプログラムまたは実装と連携して開発されました。ほとんどのWebベースのツールでは、FASTA形式やGenBank形式など、限られた数の入出力形式が許可されており、出力は簡単に編集できません。READSEQやEMBOSSなど、グラフィカルおよび/またはコマンドラインインターフェイスを提供する変換プログラムがいくつか利用可能です^{[リンク切れ‍ ]} 。また、 BioPython、 BioRuby、BioPerlなど、この変換機能を提供するプログラミングパッケージもいくつかあります。SAM/BAMファイルは、 CIGAR（Compact Idiosyncratic Gapped Alignment Report）文字列形式を使用して、一連のイベント（一致/不一致、挿入、削除など）をエンコードすることにより、参照に対する配列のアライメントを表します。^[6]

参照: 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の長さと等しくなります。

グローバルアラインメントは、すべての配列のすべての残基をアラインメントしようとするもので、クエリセット内の配列が類似しており、ほぼ同じサイズである場合に最も有用である。（これは、グローバルアラインメントがギャップで開始および/または終了できないことを意味するものではない。）一般的なグローバルアラインメント手法は、動的プログラミングに基づくニードルマン・ヴンシュアルゴリズムである。ローカルアラインメントは、より大きな配列コンテキスト内に類似領域または類似の配列モチーフが含まれていると疑われる非類似配列に対してより有用である。スミス・ウォーターマンアルゴリズムは、同じ動的プログラミングスキームに基づく一般的なローカルアラインメント手法であるが、任意の場所で開始および終了する追加の選択肢がある。^[4]

ハイブリッド法はセミグローバル法または「グローカル」（グローバルローカルの略）法とも呼ばれ、2 つの配列の可能な限り最良の部分的なアラインメント（つまり、一方または両方の開始と一方または両方の終了の組み合わせがアラインメントされているとされる）を検索します。これは、一方の配列の下流部分がもう一方の配列の上流部分と重複している場合に特に役立ちます。この場合、グローバル アラインメントもローカル アラインメントも完全には適切ではありません。グローバル アラインメントは、アラインメントを重複領域を超えて拡張しようとしますが、ローカル アラインメントは重複領域を完全にはカバーしない可能性があります。^[7]セミグローバル アラインメントが役立つもう 1 つのケースは、一方の配列が短く（たとえば、遺伝子配列）、もう一方の配列が非常に長い（たとえば、染色体配列）場合です。その場合、短い配列はグローバルに（完全に）アラインメントする必要がありますが、長い配列にはローカル（部分的）アラインメントのみが必要です。

遺伝子データの急速な拡大は、現在の DNA 配列アライメント アルゴリズムの速度に課題をもたらします。DNA 変異体を発見するための効率的で正確な方法には、リアルタイムで並列処理するための革新的なアプローチが不可欠です。光コンピューティングアプローチは、現在の電気的実装の有望な代替手段として提案されていますが、その適用性はまだテストされていません [1]。

ペアワイズ配列アライメント法は、2 つのクエリ配列の最も一致する部分的 (ローカルまたはグローバル) アライメントを見つけるために使用されます。ペアワイズ アライメントは一度に 2 つの配列間でのみ使用できますが、計算が効率的であり、極端な精度を必要としない方法 (クエリと高い類似性を持つ配列をデータベースで検索するなど) でよく使用されます。ペアワイズ アライメントを作成する 3 つの主な方法は、ドット マトリックス法、動的プログラミング、およびワード法です。^{[1]ただし、複数の配列アライメント技術を使用して、配列のペアをアライメントすることもできます。各方法にはそれぞれ長所と短所がありますが、3 つのペアワイズ法はすべて、}情報量が少なく反復が多い配列(特に、アライメントする 2 つの配列で反復数が異なる場合) の処理が困難です。

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

より正確には:

「2つのゲノムAとBが与えられた場合、最大ユニークマッチ（MUM）部分文字列は、指定された最小長さd（デフォルトではd=20）よりも長いAとBの共通部分文字列であり、

• それは最大であり、つまり、ミスマッチを生じさせずにどちらの端にも拡張することはできない。
• それは両方の配列においてユニークである」^[9]

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

ドット プロットを情報表示手法として使用する場合の問題としては、ノイズ、明瞭性の欠如、直感性の欠如、2 つのシーケンス上の一致概要統計と一致位置の抽出の難しさなどがあります。また、一致データが本質的に対角線上で重複し、プロットの実際の領域の大部分が空きスペースまたはノイズで占められるため、無駄なスペースが多くあります。最後に、ドット プロットは 2 つのシーケンスに制限されます。これらの制限はいずれも Miropeats アラインメント ダイアグラムには当てはまりませんが、独自の欠点があります。

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

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

ダイナミック プログラミングは、ヌクレオチド配列をタンパク質配列にアラインメントする際に役立ちます。この作業は、フレームシフト変異 (通常は挿入または削除) を考慮する必要があるため複雑になります。フレームサーチ法は、クエリ ヌクレオチド配列と検索タンパク質配列セットの間、またはその逆の一連のグローバルまたはローカルなペアワイズ アラインメントを作成します。任意の数のヌクレオチドでオフセットされたフレームシフトを評価できるため、この方法は、より効率的なヒューリスティック法でアラインメントするのが非常に難しい、多数のインデルを含む配列に役立ちます。実際には、この方法には大量の計算能力、またはダイナミック プログラミングに特化したアーキテクチャを持つシステムが必要です。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 つ以上の配列を組み込むものです。多重アライメント法では、特定のクエリ セット内のすべての配列をアライメントしようとします。多重アライメントは、進化的に関連すると仮定される配列のグループ全体で保存された配列領域を識別するためによく使用されます。このような保存された配列モチーフは、酵素の触媒活性部位を見つけるために、構造情報や機構情報と組み合わせて使用​​できます。アライメントは、系統樹を構築して進化関係を確立するのにも使用されます。多重配列アライメントは計算上作成が難しく、問題のほとんどの定式化はNP 完全組み合わせ最適化問題につながります。^{[12] [13]}それにもかかわらず、バイオインフォマティクスにおけるこれらのアライメントの有用性により、3 つ以上の配列をアライメントするのに適したさまざまな方法が開発されました。

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

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

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

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

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

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

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

構造アライメントは、通常はタンパク質、時にはRNA配列に特有のもので、タンパク質またはRNA分子の二次構造と三次構造に関する情報を使用して、配列のアライメントを支援します。これらの方法は、2つ以上の配列に使用でき、通常はローカルアライメントを生成します。ただし、構造情報の可用性に依存するため、対応する構造がわかっている配列（通常はX線結晶構造解析またはNMR分光法による）にのみ使用できます。タンパク質とRNAの構造はどちらも配列よりも進化的に保存されているため、^[21]構造アライメントは、非常に遠い関係にある配列や、配列比較では類似性を確実に検出できないほど大幅に分岐した配列の間では、より信頼性が高くなる可能性があります。

構造アラインメントは、配列情報のみに頼るのではなく、構造的に類似したタンパク質配列の領域を明示的にアラインメントするため、相同性に基づくタンパク質構造予測のアラインメントを評価する「ゴールド スタンダード」として使用されます^[22]。ただし、クエリ セット内の少なくとも 1 つの配列がモデル化の対象となるターゲットであり、その構造が不明であるため、構造アラインメントを構造予測に使用することはできません。ターゲットとテンプレート配列間の構造アラインメントが与えられれば、ターゲット タンパク質配列の非常に正確なモデルを作成できることが示されています。相同性に基づく構造予測の大きな障害は、配列情報のみを与えられた場合に構造的に正確なアラインメントを作成することです^{[22] 。}

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

SSAP（シーケンシャル構造アライメントプログラム）は、構造空間内の原子間ベクトルを比較ポイントとして使用する動的プログラミングベースの構造アライメント法です。この方法は、最初の記述から拡張され、複数のアライメントとペアワイズアライメントが含まれるようになりました。 ^{[24]また、タンパク質フォールドの}CATH（クラス、アーキテクチャ、トポロジー、ホモロジー）階層データベース分類の構築にも使用されています。 ^[25] CATHデータベースは、CATH Protein Structure Classificationからアクセスできます。

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

系統学と配列アライメントは、配列の関連性を評価するという共通の必要性から、密接に関連した分野である。^[27]系統学の分野では、分岐種のゲノムに表される相同遺伝子間の進化的関係を分類するために使用される系統樹の構築と解釈において、配列アライメントが広く使用されている。クエリセット内の配列が異なる程度は、配列間の進化的距離に定性的に関連している。大まかに言えば、高い配列同一性は、問題の配列が比較的最近の共通祖先を持つことを示唆し、低い同一性は、分岐がより古いことを示唆している。この近似は、進化の変化のほぼ一定の速度を使用して、2つの遺伝子が最初に分岐してからの経過時間（つまり、融合時間）を推定できるという「分子時計」仮説を反映しており、突然変異と選択の影響は配列系統全体で一定であると仮定している。したがって、生物や種によってDNA 修復速度が異なる可能性や、配列内の特定領域の機能的保存の可能性は考慮されません。(ヌクレオチド配列の場合、最も基本的な形の分子時計仮説では、特定のコドンの意味を変えないサイレント変異と、異なるアミノ酸がタンパク質に組み込まれる他の変異との間の受容率の違いも考慮されません)。より統計的に正確な方法を使用すると、系統樹の各枝の進化速度を変えることができるため、遺伝子の合体時期をより正確に推定できます。

漸進的多重アラインメント技術は、関連性の順に配列を組み込むため、必然的に系統樹を生成します。多重配列アラインメントと系統樹を組み立てる他の技術では、最初にツリーにスコアを付けて並べ替え、最もスコアの高いツリーから多重配列アラインメントを計算します。系統樹構築によく使用される方法は主にヒューリスティックです。最適なツリーを選択する問題は、最適な多重配列アラインメントを選択する問題と同様に、NP困難であるためです。^[28]

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

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

ギャップ配列アラインメントの統計的有意性推定の方法は文献に記載されている。^{[27] [29] [30] [31] [32] [33] [34] [35]}

統計的有意性は、特定の品質のアラインメントが偶然に発生する可能性を示しますが、特定のアラインメントが同じ配列の代替アラインメントよりもどれだけ優れているかを示すものではありません。アラインメントの信頼性の尺度は、特定の配列ペアの最高スコアのアラインメントが実質的にどの程度類似しているかを示します。ギャップのある配列アラインメントのアラインメント信頼性推定の方法は、文献で入手できます。^[36]

既知の配列に関する生物学的または統計的観察を反映するスコアリング関数の選択は、良好なアラインメントを生成するために重要です。タンパク質配列は、特定の文字間の置換の確率を反映する置換マトリックスを使用してアラインメントされることがよくあります。PAMマトリックス(Point Accepted Mutation マトリックス、Margaret Dayhoffによって最初に定義され、「Dayhoff マトリックス」と呼ばれることもあります) と呼ばれる一連のマトリックスは、特定のアミノ酸変異の率と確率に関する進化的近似を明示的にエンコードします。BLOSUM (Blocks Substitution Matrix) として知られる別の一般的なスコアリング マトリックスは、経験的に導き出された置換確率をエンコードします。両方のタイプのマトリックスのバリアントは、異なるレベルの相違を持つ配列を検出するために使用されます。これにより、BLAST または FASTA のユーザーは、検索をより関連性の高い一致に制限したり、より異なる配列を検出するように拡張したりできます。ギャップ ペナルティは、ヌクレオチド配列とタンパク質配列の両方におけるギャップ (進化モデルでは挿入または削除変異) の導入を考慮したもので、したがってペナルティ値はそのような変異の予想率に比例する必要があります。したがって、生成されるアラインメントの品質は、スコアリング関数の品質に依存します。

スコアリング マトリックスやギャップ ペナルティ値に異なる選択肢を与えて同じアライメントを数回試し、結果を比較することは非常に有用で有益です。アライメントのどの領域がアライメント パラメータの変化に対して堅牢であるかを観察することで、ソリューションが弱い、または一意でない領域を特定できることがよくあります。

発現配列タグや全長mRNAなどの配列決定されたRNAは、配列決定されたゲノムに整列させて遺伝子がどこにあるかを見つけ、選択的スプライシング^[37]やRNA編集^[38]に関する情報を得ることができます。配列アライメントはゲノムアセンブリの一部でもあり、配列を整列させて重複を見つけ、コンティグ（長い配列）を形成します。^[39]もう1つの用途はSNP分析で、異なる個体からの配列を整列させて、集団内で異なることが多い単一の塩基対を見つけます。^[40]

生物学的配列アライメントに使用される方法は、他の分野、特に自然言語処理や社会科学にも応用されており、ニードルマン・ヴンシュアルゴリズムは通常、最適マッチングと呼ばれています。^[41]自然言語生成アルゴリズムで単語が選択される要素セットを生成する技術は、バイオインフォマティクスから多重配列アライメント技術を借用して、コンピューター生成の数学的証明の言語バージョンを作成しました。^{[42]歴史言語学と比較}言語学の分野では、配列アライメントは、言語学者が伝統的に言語を再構築する比較方法を部分的に自動化するために使用されてきました。[43]ビジネスおよびマーケティング研究では、時間の経過に伴う一連の購入を分析するために多重配列アライメント技術も適用されています。 [ ^{44 ]}

利用可能なソフトウェアのより完全なリストは、アルゴリズムとアライメントタイプ別に分類されており、配列アライメントソフトウェアで入手できますが、一般的な配列アライメントタスクに使用される一般的なソフトウェアツールには、アライメント用のClustalW2 ^[45]とT-coffee ^[46]、データベース検索用のBLAST ^[47]とFASTA3x ^[48]があります。DNASTAR Lasergene、Geneious、PatternHunterなどの市販ツールも利用できます。配列アライメントを実行すると注釈が付けられたツールは、bio.toolsレジストリにリストされています。

アライメントアルゴリズムとソフトウェアは、BAliBASEとして知られる標準化されたベンチマーク参照多重配列アライメントセットを使用して直接比較することができます。 ^[49]データセットは構造アライメントで構成されており、純粋に配列ベースの方法を比較するための基準と考えることができます。頻繁に発生するアライメント問題に対する多くの一般的なアライメント方法の相対的なパフォーマンスは表にまとめられており、選択された結果はBAliBASEでオンラインで公開されています。^{[50] [51]}多くの（現在12）異なるアライメントツールのBAliBASEスコアの包括的なリストは、タンパク質ワークベンチSTRAP内で計算できます。^[52]

• 配列相同性
• シーケンスマイニング
• ブラスト
• 文字列検索アルゴリズム
• アライメントフリー配列解析
• ウゲネ
• ニードルマン・ヴンシュアルゴリズム
• スミス・ウォーターマンアルゴリズム
• 社会科学におけるシーケンス分析

Wikiversityにはドットマトリックス法に関する学習リソースがあります

この記事を聞く（39分）

この音声ファイルは、2012 年 6 月 5 日付のこの記事の改訂版から作成されたもので、その後の編集は反映されていません。 ( 2012-06-05 )

(音声ヘルプ ·その他の音声記事)

• ウィキメディア・コモンズの配列アラインメントに関連するメディア