配列アラインメント

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

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

哺乳類のヒストンタンパク質のClustalOによって生成された配列アラインメント。配列は、タンパク質の残基120〜180のアミノ酸です。すべてのシーケンスで保存されている残基は灰色で強調表示されています。タンパク質配列の下には、保存配列(*)、保存変異(:)、半保存変異(。)、および非保存変異()を示すキーがあります[2]

解釈

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

位置合わせ方法

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

表現

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

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

CIGARフォーマット

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

exonerateアライメントプログラムからの元のCIGAR形式は、M文字との不一致または一致を区別しませんでした。

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

CIGARコード BAM整数 説明 クエリを消費します 参照を消費します
M 0 アラインメントの一致(シーケンスの一致または不一致の場合があります) はい はい
1 参照への挿入 はい いいえ
D 2 参照からの削除 いいえ はい
N 3 参照からスキップされた領域 いいえ はい
S 4 ソフトクリッピング(SEQに存在するクリップされたシーケンス) はい いいえ
H 5 ハードクリッピング(CLIPされたシーケンスはSEQに存在しません) いいえ いいえ
P 6 パディング(パディングされた参照からのサイレント削除) いいえ いいえ
= 7 シーケンスマッチ はい はい
バツ 8 シーケンスの不一致 はい はい
  • 「consumesquery」と「consumesreference」は、CIGAR操作によってアライメントがそれぞれクエリシーケンスとリファレンスシーケンスに沿って進むかどうかを示します。
  • Hは、最初および/または最後の操作としてのみ存在できます。
  • Sは、それらとCIGAR文字列の終わりとの間にH演算のみを持つことができます。
  • mRNAからゲノムへのアラインメントの場合、N操作はイントロンを表します。他のタイプのアライメントの場合、Nの解釈は定義されていません。
  • M / I / S / = / X演算の長さの合計は、SEQの長さと等しくなります。

グローバルおよびローカルアラインメント

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

セミグローバルまたは「グローカル」( glo bal-lo calの略)メソッドとして知られるハイブリッドメソッドは、2つのシーケンスの可能な限り最良の部分アラインメント(つまり、一方または両方の開始と一方または両方の組み合わせ)を検索します。端は整列していると述べられています)。これは、一方のシーケンスの下流部分がもう一方のシーケンスの上流部分とオーバーラップする場合に特に役立ちます。この場合、グローバルアラインメントもローカルアラインメントも完全に適切ではありません。グローバルアラインメントは、アラインメントをオーバーラップ領域を超えて拡張しようとしますが、ローカルアラインメントはオーバーラップ領域を完全にカバーしない場合があります。[7]セミグローバルアラインメントが役立つもう1つのケースは、一方の配列が短く(たとえば、遺伝子配列)、もう一方の配列が非常に長い場合(たとえば、染色体配列)です。その場合、短いシーケンスはグローバルに(完全に)整列する必要がありますが、長いシーケンスにはローカル(部分)の整列のみが必要です。

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

ペアワイズアラインメント

ペアワイズシーケンスアラインメントメソッドは、2つのクエリシーケンスの最適な区分的(ローカルまたはグローバル)アラインメントを見つけるために使用されます。ペアワイズアラインメントは、一度に2つのシーケンス間でのみ使用できますが、計算が効率的であり、極端な精度を必要としないメソッド(データベースでクエリとの類似性が高いシーケンスを検索するなど)によく使用されます。ペアワイズアラインメントを生成する3つの主要な方法は、ドットマトリックス法、動的計画法、および単語法です。[1]ただし、マルチプルアラインメント手法では、シーケンスのペアをアラインメントすることもできます。それぞれの方法にはそれぞれ長所と短所がありますが、3つのペアワイズ法はすべて、情報量の少ないシーケンスを繰り返し実行するのが困難です。-特に、整列する2つのシーケンスで繰り返し回数が異なる場合。

最大の一意の一致

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

より正確に:

「2つのゲノムAとBが与えられた場合、Maximal Unique Match(MUM)サブストリングは、指定された最小長d(デフォルトではd = 20)よりも長いAとBの一般的なサブストリングです。

  • これは最大です。つまり、不一致が発生することなく、どちらの端でも拡張することはできません。
  • それは両方のシーケンスでユニークです」[9]

ドットマトリックスメソッド

マウス系統ゲノムの一部の自己比較。ドットプロットは線のパッチワークを示しており、DNAの複製されたセグメントを示しています。
ヒトジンクフィンガー転写因子(GenBank ID NM_002383)のDNAドットプロット。地域の自己相似示しています。主対角線は、シーケンスとそれ自体との位置合わせを表します。主対角線から外れた線は​​、シーケンス内の類似または反復パターンを表します。これは、リカレンスプロットの典型的な例です。

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

情報表示手法としてのドットプロットの問題には、ノイズ、明瞭さの欠如、直感的でないこと、2つのシーケンスの一致要約統計量と一致位置の抽出の難しさが含まれます。また、一致データが対角線全体で本質的に複製され、プロットの実際の領域のほとんどが空のスペースまたはノイズによって占められ、最後にドットプロットが2つのシーケンスに制限される多くの無駄なスペースがあります。これらの制限はいずれもMiropeatsの配置図には適用されませんが、固有の欠陥があります。

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

動的計画法

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

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

動的計画法は、特定のスコアリング関数が与えられた場合に最適な配置を見つけることが保証されています。ただし、適切なスコアリング関数を特定することは、理論的な問題ではなく、経験的な問題であることがよくあります。動的計画法は3つ以上のシーケンスに拡張可能ですが、多数のシーケンスまたは非常に長いシーケンスでは非常に低速です。

Wordメソッド

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

FASTA法では、ユーザーはデータベースを検索するための語長として使用する値kを定義します。この方法は低速ですが、kの値が低いほど感度が高くなります。これは、非常に短いクエリシーケンスを含む検索にも適しています。BLASTファミリーの検索メソッドは、遠縁のシーケンス一致の検索など、特定のタイプのクエリ用に最適化された多数のアルゴリズムを提供します。BLASTは、精度をあまり犠牲にすることなく、FASTAのより高速な代替手段を提供するために開発されました。FASTAと同様に、BLASTは長さkの単語検索を使用します、ただし、FASTAのようにすべての単語の一致ではなく、最も重要な単語の一致のみを評価します。ほとんどのBLAST実装は、クエリとデータベースタイプに最適化された固定のデフォルトの単語長を使用します。これは、繰り返しまたは非常に短いクエリシーケンスで検索する場合など、特別な状況でのみ変更されます。実装は、 EMBLFASTANCBIBLASTなどの多くのWebポータルを介して見つけることができます

マルチプルアラインメント

残基保存(上)と残基特性(下)によって着色された27の鳥インフルエンザ 血球凝集素タンパク質配列のアラインメント

マルチプルアラインメントは、ペアワイズアラインメントを拡張したもので、一度に3つ以上の配列を組み込むことができます。複数のアラインメントメソッドは、特定のクエリセット内のすべてのシーケンスをアラインメントしようとします。マルチプルアラインメントは、進化的に関連していると仮定された配列のグループ全体で保存された配列領域を識別する際によく使用されます。このような保存された配列モチーフは、酵素の触媒活性部位を特定するための構造的および機構的情報と組み合わせて使用​​することができますアラインメントは、系統樹を構築することによって進化的関係を確立するのを支援するためにも使用されます複数の配列アラインメントを作成することは計算上困難であり、問​​題のほとんどの定式化はNP完全な組み合わせ最適化問題につながります。[10] [11]それにもかかわらず、バイオインフォマティクスにおけるこれらのアラインメントの有用性は、3つ以上の配列をアラインメントするのに適したさまざまな方法の開発につながりました。

動的計画法

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

プログレッシブメソッド

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

Clustalプログレッシブ実装の多くのバリエーション[13] [14] [15]は、マルチプルアラインメント、系統樹の構築、およびタンパク質構造予測の入力として使用されます。プログレッシブメソッドの低速ですがより正確な変形は、T-Coffeeとして知られています。[16]

反復法

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

モチーフ検索

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

コンピュータサイエンスに触発された技術

マルチプルアラインメントをモデル化したプロファイルHMM

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

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

構造アラインメント

通常はタンパク質および場合によってはRNA配列に固有の構造アラインメントは、タンパク質またはRNA分子の二次および三次構造に関する情報を使用して配列のアラインメントを支援します。これらの方法は、2つ以上の配列に使用でき、通常はローカルアラインメントを生成します。ただし、それらは構造情報の可用性に依存するため、対応する構造がわかっているシーケンスにのみ使用できます(通常はX線結晶学またはNMR分光法によって)。タンパク質とRNAの両方の構造が配列よりも進化的に保存されているため、[19]構造アラインメントは、非常に遠い関係にあり、非常に広範囲に分岐しているため、配列比較ではそれらの類似性を確実に検出できない配列間で、より信頼性が高くなる可能性があります。

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

DALI

DALI法、または距離行列アラインメントは、クエリシーケンス内の連続するヘキサペプチド間の接触類似性パターンに基づいて構造アラインメントを構築するためのフラグメントベースの方法です。[21]ペアワイズまたはマルチプルアラインメントを生成し、 Protein Data Bank(PDB)内のクエリシーケンスの構造的隣接を識別できます。これは、FSSP構造アラインメントデータベース(タンパク質の構造-構造アラインメント、または構造的に類似したタンパク質のファミリーに基づくフォールド分類)を構築するために使用されています。DALI WebサーバーはDALIでアクセスでき、FSSPはDaliデータベースにあります。

SSAP

SSAP(シーケンシャル構造アラインメントプログラム)は、構造空間内の原子間ベクトルを比較ポイントとして使用する、動的計画法に基づく構造アラインメントの方法です。元の説明から拡張され、ペアワイズアラインメントだけでなく複数のアラインメントも含まれるようになり[22] 、タンパク質フォールドのCATH(クラス、アーキテクチャ、トポロジー、ホモロジー)階層データベース分類の構築に使用されています。[23] CATHデータベースには、 CATHタンパク質構造分類でアクセスできます

組み合わせ拡張

構造アラインメントのコンビナトリアルエクステンション法は、ローカルジオメトリを使用して、分析対象の2つのタンパク質の短いフラグメントをアラインメントし、これらのフラグメントをより大きなアラインメントにアセンブルすることにより、ペアワイズ構造アラインメントを生成します。[24]剛体の二乗平均平方根距離、残基距離、局所的な二次構造、および残基隣接疎水性などの周囲の環境的特徴などの測定に基づく、「アラインメントされたフラグメントペア」と呼ばれるローカルアラインメントが生成され、事前定義されたカットオフ基準内のすべての可能な構造アラインメントを表す類似性マトリックスを構築するために使用されます。次に、あるタンパク質構造状態から別のタンパク質構造状態へのパスは、成長するアラインメントを一度に1フラグメントずつ拡張することにより、マトリックスを介してトレースされます。このような最適なパスは、組み合わせと拡張のアラインメントを定義します。この方法を実装し、Protein Data Bankの構造のペアワイズアラインメントのデータベースを提供するWebベースのサーバーは、Combinatorial ExtensionWebサイトにあります。

系統発生分析

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

プログレッシブマルチプルアラインメント技術は、関連性の順に成長するアラインメントに配列を組み込むため、必然的に系統樹を生成します。複数の配列アラインメントと系統樹を組み立てる他の手法では、最初にツリーをスコアリングしてソートし、最高スコアのツリーから複数の配列アラインメントを計算します。最適なマルチプルアラインメントの選択の問題のように、最適なツリーの選択の問題はNP困難であるため、系統樹の構築に一般的に使用される方法は主にヒューリスティックです。[26]

重要性の評価

配列アラインメントは、配列の類似性を識別し、系統樹を作成し、タンパク質構造のホモロジーモデルを開発するためのバイオインフォマティクスで役立ちます。ただし、配列アラインメントの生物学的関連性は必ずしも明確ではありません。アラインメントは、共通の祖先から派生したシーケンス間の進化的変化の程度を反映していると見なされることがよくあります。ただし、収斂進化が発生して、進化的には無関係であるが、同様の機能を実行し、同様の構造を持つタンパク質間に明らかな類似性が生じる可能性があります。

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

ギャップのある配列アラインメントの統計的有意性推定の方法は、文献で利用可能です。[25] [27] [28] [29] [30] [31] [32] [33]

信頼性の評価

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

スコアリング関数

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

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

その他の生物学的用途

発現配列タグや完全長mRNAなどの配列決定されたRNAは、配列決定されたゲノムにアラインメントして、遺伝子が存在する場所を見つけ、選択的スプライシング[35]およびRNA編集に関する情報を取得できます。[36]配列アラインメントもゲノムアセンブリの一部であり、コンティグ(配列の長いストレッチ)を形成できるように、配列をアラインメントしてオーバーラップを見つけます。[37]別の用途はSNP分析であり、異なる個体からの配列を整列させて、集団内でしばしば異なる単一の塩基対を見つけます。[38]

非生物学的用途

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

ソフトウェア

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

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

も参照してください

参考文献

  1. ^ a bcDM をマウントします。(2004)。バイオインフォマティクス:シーケンスおよびゲノム分析(第2版)。コールドスプリングハーバーラボラトリープレス:ニューヨーク州コールドスプリングハーバー。ISBN 978-0-87969-608-5
  2. ^ 「ClustalFAQ#Symbols」Clustal2016年10月24日にオリジナルからアーカイブされました2014年12月8日取得
  3. ^ Ng PC; ヘニコフS(2001年5月)。「有害なアミノ酸置換の予測」GenomeRes11(5):863–74。土井10.1101 /gr.176601PMC311071_ PMID11337480_  
  4. ^ a b ポリアノフスキー、VO; マサチューセッツ州ロイトバーグ; トゥマニヤン、VG(2011)。「2つのシーケンスのアラインメントのためのグローバルアルゴリズムとローカルアルゴリズムの品質の比較分析」分子生物学のアルゴリズム6(1):25。doi10.1186 / 1748-7188-6-25PMC3223492_ PMID22032267_ S2CID2658261_   
  5. ^ シュナイダーTD; スティーブンスRM(1990)。「シーケンスロゴ:コンセンサスシーケンスを表示する新しい方法」Nucleic AcidsRes18(20):6097–6100。土井10.1093 / nar /18.20.6097PMC332411_ PMID2172928_  
  6. ^ 「シーケンスアラインメント/マップフォーマット仕様」(PDF)
  7. ^ Brudno M; マルデS; ポリアコフA; CBを行う; Couronne O; Dubchak I; Batzoglou S(2003)。「グローカルアラインメント:アラインメント中に再配置を見つける」バイオインフォマティクス19.補足1(90001):i54–62。土井10.1093 / bioinformatics / btg1005PMID12855437_ 
  8. ^ デルチャー、AL; Kasif、S。; Fleishmann、RD; ピーターソン、J。; ホワイト、O。; Salzberg、SL(1999)。「全ゲノムのアラインメント」核酸研究27(11):2369–2376。土井10.1093 / nar /30.11.2478PMC148804_ PMID10325427_  
  9. ^ ウィングキン、ソン(2010)。バイオインフォマティクスのアルゴリズム:実用的な紹介(初版)。ボカラトン:チャップマン&ホール/ CRCプレス。ISBN 978-1420070330
  10. ^ 王L; 江T.(1994)。「マルチプルアラインメントの複雑さについて」。J ComputBiol1(4):337–48。CiteSeerX10.1.1.408.894_ 土井10.1089 /cmb.1994.1.337PMID8790475_  
  11. ^ エリアス、アイザック(2006)。「マルチプルアラインメントの難しさを解決する」。J ComputBiol13(7):1323–1339。CiteSeerX10.1.1.6.256_ 土井10.1089 /cmb.2006.13.1323PMID17037961_  
  12. ^ リップマンDJ; アルツシュルSF; Kececioglu JD(1989)。「マルチプルアラインメントのためのツール」Proc Natl Acad SciUSA86(12):4412–5。Bibcode1989PNAS ... 86.4412L土井10.1073 /pnas.86.12.4412PMC287279_ PMID2734293_  
  13. ^ Higgins DG、Sharp PM(1988)。「CLUSTAL:マイクロコンピューターでマルチプルアラインメントを行うためのパッケージ」。遺伝子73(1):237–44。土井10.1016 / 0378-1119(88)90330-7PMID3243435_ 
  14. ^ トンプソンJD; ヒギンズDG ; ギブソンTJ。(1994)。「CLUSTALW:シーケンスの重み付け、位置固有のギャップペナルティ、およびウェイトマトリックスの選択により、プログレッシブマルチプルアラインメントの感度を向上させます」Nucleic AcidsRes22(22):4673–80。土井10.1093 / nar /22.22.4673PMC308517_ PMID7984417_  
  15. ^ Chenna R; 菅原H; 小池T; ロペスR; ギブソンTJ; ヒギンズDG; トンプソンJD。(2003)。「Clustalシリーズのプログラムとのマルチプルアラインメント」Nucleic AcidsRes31(13):3497–500。土井10.1093 / nar / gkg500PMC168907_ PMID12824352_  
  16. ^ Notredame C; ヒギンズDG ; ヘリンガJ.(2000)。「T-Coffee:高速かつ正確なマルチプルアラインメントのための新しい方法」J MolBiol302(1):205–17。土井10.1006 /jmbi.2000.4042PMID10964570_ S2CID10189971_  
  17. ^ 廣沢M; トトキY; 星田M; 石川正明(1995)。「マルチプルアラインメントの反復アルゴリズムに関する包括的な研究」。ApplBiosciを計算します。11(1):13–8。土井10.1093 / bioinformatics /11.1.13PMID7796270_ 
  18. ^ Karplus K; バレットC; ヒューイR.(1998)。「遠隔タンパク質相同性を検出するための隠れマルコフモデル」バイオインフォマティクス14(10):846–856。土井10.1093 / bioinformatics /14.10.846PMID9927713_ 
  19. ^ チョーシアC; レスクAM。(1986年4月)。「タンパク質の配列と構造の相違の関係」EMBOJ5(4):823–6。土井10.1002 /j.1460-2075.1986.tb04288.xPMC1166865_ PMID3709526_  
  20. ^ a b Zhang Y; Skolnick J.(2005)。「タンパク質構造予測の問題は、現在のPDBライブラリを使用して解決できます」Proc Natl Acad SciUSA102(4):1029–34。Bibcode2005PNAS..102.1029Z土井10.1073 /pnas.0407152101PMC545829_ PMID15653774_  
  21. ^ ホルムL; サンダーC(1996)。「タンパク質宇宙のマッピング」科学273(5275):595–603。Bibcode1996Sci ... 273..595H土井10.1126 /science.273.5275.595PMID8662544_ S2CID7509134_  
  22. ^ テイラーWR; フローレスTP; オレンゴCA。(1994)。「複数のタンパク質構造アラインメント」タンパク質科学3(10):1858–70。土井10.1002 /pro.5560031025PMC2142613_ PMID7849601_  
  23. ^ Orengo CA; Michie AD; ジョーンズS; ジョーンズDT; スウィンデルズMB; ソーントンJM(1997)。「CATH--タンパク質ドメイン構造の階層的分類」構造5(8):1093–108。土井10.1016 / S0969-2126(97)00260-8PMID9309224_ 
  24. ^ シンディアロフIN; ボーンPE。(1998)。「最適パスのインクリメンタルコンビナトリアルエクステンション(CE)によるタンパク質構造アラインメント」ProteinEng11(9):739–47。土井10.1093 / protein /11.9.739PMID9796821_ 
  25. ^ a b Ortet P; バスティアンO(2010)。「アライメントスコアの分布の形はどこから来たのですか?」進化生物学6:159–187。土井10.4137 /EBO.S5875PMC3023300_ PMID21258650_  
  26. ^ フェルゼンシュタインJ.(2004)。系統発生を推測する。Sinauer Associates:マサチューセッツ州サンダーランド。ISBN 978-0-87893-177-4
  27. ^ Altschul SF; ギッシュW(1996)。ローカルアライメント統計Meth.Enz酵素学の方法。266. pp。460–480。土井10.1016 / S0076-6879(96)66029-7ISBN 9780121821678PMID8743700 _
  28. ^ Hartmann AK(2002)。「まれなイベントのサンプリング:ローカルシーケンスアラインメントの統計」物理学 牧師E。65(5):056102。arXiv cond -mat / 0108201Bibcode2002PhRvE..65e6102H土井10.1103 /PhysRevE.65.056102PMID12059642_ S2CID193085_  
  29. ^ ニューバーグLA(2008)。「ギャップのある配列アラインメントの重要性」J ComputBiol15(9):1187–1194。土井10.1089 /cmb.2008.0125PMC2737730_ PMID18973434_  
  30. ^ Eddy SR; Rost、Burkhard(2008)。ロスト、ブルクハルト(編)。「統計的有意性の推定を単純化するローカル配列アラインメントの確率モデル」PLOS ComputBiol4(5):e1000069。Bibcode2008PLSCB ... 4E0069E土井10.1371 /journal.pcbi.1000069PMC2396288_ PMID18516236_ S2CID15640896_   
  31. ^ バスティアンO; Aude JC; ロイS; マレシャルE(2004)。「タンパク質配列の大規模な自動ペアワイズアラインメントの基礎:Z値統計の理論的有意性」バイオインフォマティクス20(4):534–537。土井10.1093 / bioinformatics / btg440PMID14990449_ 
  32. ^ アグラワルA; 黄X(2011)。「シーケンス固有および位置固有の置換行列を使用したローカルシーケンスアラインメントのペアワイズ統計的有意性」計算生物学とバイオインフォマティクスに関するIEEE / ACMトランザクション8(1):194–205。土井10.1109 /TCBB.2009.69PMID21071807_ S2CID6559731_  
  33. ^ アグラワルA; ブレンデルVP; 黄X(2008)。「タンパク質の局所配列アラインメントに対する効果的なギャップ開口ペナルティのペアワイズ統計的有意性と経験的決定」計算生物学と薬物設計の国際ジャーナル1(4):347–367。土井10.1504 /IJCBDD.2008.022207PMID20063463_ 2013年1月28日にオリジナルからアーカイブされました。 
  34. ^ ニューバーグLA; ローレンスCE(2009)。「整数の分布の正確な計算、シーケンスアラインメントへの適用」J ComputBiol16(1):1–18。土井10.1089 /cmb.2008.0137PMC2858568_ PMID19119992_  
  35. ^ キムN; リーC(2008)。選択的スプライシングのバイオインフォマティクス検出分子生物学の方法。452. pp。179–97。土井10.1007 / 978-1-60327-159-2_9ISBN 978-1-58829-707-5PMID18566765 _
  36. ^ Li JB、Levanon EY、Yoon JK、他。(2009年5月)。「並行DNAキャプチャーとシーケンシングによるヒトRNA編集部位のゲノムワイドな同定」科学324(5931):1210–3。Bibcode2009Sci ... 324.1210L土井10.1126 /science.11​​70995PMID19478186_ S2CID31148824_  
  37. ^ Blazewicz J、Bryja M、Figlerowicz M、他。(2009年6月)。「修正されたDNAグラフの概念による454シーケンス出力からの全ゲノムアセンブリ」。Comput BiolChem33(3):224–30。土井10.1016 /j.compbiolchem.2009.04.005PMID19477687_ 
  38. ^ デュランC; Appleby N; ヴァーディM; Imelfort M; エドワーズD; バットレイJ(2009年5月)。「autoSNPdbを使用したオオムギの一塩基多型の発見」植物バイオテクノロジー。J。 _ 7(4):326–33。土井10.1111 /j.1467-7652.2009.00407.xPMID19386041_ 
  39. ^ アボットA .; Tsay A.(2000)「社会学、レビューおよび展望におけるシーケンス分析および最適なマッチング方法」。社会学的方法と研究29(1):3–33。土井10.1177 / 0049124100029001001S2CID121097811_ 
  40. ^ Barzilay R; Lee L.(2002)。「マルチプルアラインメントによるブートストラップレキシカルチョイス」(PDF)自然言語処理における経験的方法に関する会議の議事録(EMNLP)10:164–171。arXivcs / 0205065Bibcode2002cs ........ 5065B土井10.3115 /1118693.1118715S2CID7521453_  
  41. ^ Kondrak、Grzegorz(2002)。「言語再構築のアルゴリズム」(PDF)トロント大学、オンタリオ。2008年12月17日にオリジナル(PDF)からアーカイブされました2007年1月21日取得 {{cite journal}}引用ジャーナルには|journal=ヘルプ)が必要です
  42. ^ Prinzie A。; D.ヴァンデンポール(2006)。「要素/位置に依存するSAMを使用して、従来の分類モデルにシーケンシャル情報を組み込む」意思決定支援システム42(2):508–526。土井10.1016 /j.dss.2005.02.004PrinzieとVanden Poelの論文Prinzie、Aも参照してください。Vandenpoel、D(2007)。「家電製品の取得シーケンスの予測:NPTBモデルのシーケンシャル情報をモデル化するための識別と生存分析のためのマルコフ/マルコフ」意思決定支援システム44(1):28–45。土井10.1016 /j.dss.2007.02.008
  43. ^ EMBL-EBI。"ClustalW2 <マルチプルアラインメント<EMBL-EBI"www.EBI.ac.uk。_ 2017年6月12日取得
  44. ^ T-コーヒー
  45. ^ 「BLAST:基本的なローカルアライメント検索ツール」blast.ncbi.nlm.NIH.gov 2017年6月12日取得
  46. ^ 「UVAFASTAサーバー」fasta.bioch.Virginia.edu 2017年6月12日取得
  47. ^ トンプソンJD; Plewniak F; Poch O(1999)。「BAliBASE:複数のアラインメントプログラムを評価するためのベンチマークアラインメントデータベース」バイオインフォマティクス15(1):87–8。土井10.1093 / bioinformatics /15.1.87PMID10068696_ 
  48. ^ BAliBASE
  49. ^ トンプソンJD; Plewniak F; Poch O.(1999)。「マルチプルアラインメントプログラムの包括的な比較」Nucleic AcidsRes27(13):2682–90。土井10.1093 / nar /27.13.2682PMC148477_ PMID10373585_  
  50. ^ 「マルチプルアラインメント:ストラップ」3d-alignment.eu 2017年6月12日取得

外部リンク

この記事を聞く39
音声ウィキペディアアイコン
このオーディオファイルは、2012年6月5日付けのこの記事の改訂版から作成されたものであり、その後の編集は反映されていません。 (2012-06-05