ギャップペナルティ

ギャップペナルティは、2 つ以上の配列のアラインメントをスコアリングする方法です。配列をアラインメントするときに、配列にギャップを導入すると、ギャップのないアラインメントよりも多くの用語をアラインメントアルゴリズムで一致させることができます。ただし、アラインメントのギャップを最小限に抑えることは、有用なアラインメントを作成するために重要です。ギャップが多すぎると、アラインメントが意味をなさなくなる可能性があります。ギャップペナルティは、ギャップの数と長さに基づいてアラインメントスコアを調整するために使用されます。ギャップペナルティには、定数、線形、アフィン、凸型、プロファイルベースの 5 つの主な種類があります。^[1]

• 遺伝子配列アラインメント- バイオインフォマティクスでは、ギャップは、配列内の挿入または欠失から生じる遺伝子変異（インデルと呼ばれることもある）を説明するために使用されます。挿入または欠失は、単一の突然変異、減数分裂における不均衡な交差、鎖の滑りによるミスペアリング、および染色体転座によって発生する可能性があります。^[2] アラインメント内のギャップの概念は、多くの生物学的アプリケーションで重要です。挿入または欠失は、サブシーケンス全体を構成し、単一の突然変異イベントから発生することが多いためです。^[3]さらに、単一の突然変異イベントは、さまざまなサイズのギャップを作成する可能性があります。したがって、スコアリングを行う場合、2つのDNA配列をアラインメントするときに、ギャップを全体としてスコアリングする必要があります。配列内の複数のギャップを1つの大きなギャップと見なすと、突然変異に対する高いコストの割り当てが軽減されます。たとえば、2つのタンパク質配列は比較的類似している可能性がありますが、一方のタンパク質が他方のタンパク質と比較して異なるサブユニットを持つ可能性があるため、特定の間隔で異なる場合があります。これらの異なるサブシーケンスをギャップとして表すことで、シーケンス内にインデル操作を伴う長い連続実行があったとしても、これらのケースを「良好な一致」として扱うことができます。したがって、適切なギャップペナルティモデルを使用することで、アライメントのスコアが低くなることが回避され、真のアライメントを見つける可能性が高まります。^[3] 遺伝子配列アライメントでは、ギャップはタンパク質/ DNA配列アライメント上でダッシュ（-）として表されます。^[1]
• Unix diff関数- 盗作検出と同様に 2 つのファイル間の最小の差異を計算します。
• スペル チェック- ギャップ ペナルティは、スペルミスのある単語までの編集距離が最短である正しいスペルの単語を見つけるのに役立ちます。ギャップは、スペルミスのある単語に欠けている文字があることを示している可能性があります。
• 盗作検出- ギャップ ペナルティにより、アルゴリズムは元のセクションにギャップを設定し、同一の部分を一致させることで、文書のどのセクションが盗用されているかを検出できます。特定の文書のギャップ ペナルティは、特定の文書がどの程度オリジナルまたは盗用されている可能性があるかを定量化します。

グローバルアラインメントは、クエリ配列と参照配列のエンドツーエンドのアラインメントを実行します。理想的には、このアラインメント手法は、類似した長さの密接に関連した配列に最適です。ニードルマン・ヴンシュアルゴリズムは、グローバルアラインメントを実行するために使用される動的プログラミング手法です。基本的に、このアルゴリズムは問題を一連のサブ問題に分割し、サブ問題の結果を使用して元のクエリのソリューションを再構築します。^[4]

セミグローバル アラインメントは、大規模な配列内で特定の一致を見つけるために使用します。例としては、DNA 配列内のプロモーターの検索が挙げられます。グローバル アラインメントとは異なり、片方または両方の配列にエンド ギャップがないという妥協点があります。エンド ギャップが 1 つの配列 1 でペナルティを受け、配列 2 では受けていない場合は、配列 1 内に配列 2 を含むアラインメントが生成されます。

ローカル配列アラインメントは、ある配列の連続するサブセクションを別の配列の連続するサブセクションと一致させます。^[5] Smith-Waterman アルゴリズムは、一致と不一致にスコアを与えることを目的としています。一致はアラインメントの全体的なスコアを上げ、不一致はスコアを下げます。良いアラインメントは正のスコアを持ち、悪いアラインメントは負のスコアを持ちます。ローカル アルゴリズムは、正のスコアを持つアラインメントのみを考慮し、その中から最適なものを選択することで、最高スコアのアラインメントを見つけます。このアルゴリズムは動的プログラミングアルゴリズムです。タンパク質を比較する場合、可能性のある各残基ペアにスコアを割り当てる類似性マトリックスを使用します。スコアは、類似の残基に対しては正、類似しない残基ペアに対しては負になります。ギャップには通常、ギャップ開始に初期ペナルティを割り当て、ギャップ拡張に対してはギャップ長を増やす追加のペナルティを割り当てる線形ギャップ関数を使用してペナルティが課されます。

BLOSUMなどの置換マトリックスは、タンパク質の配列アラインメントに使用されます。^[6]置換マトリックスは、残基の可能なペアをアラインメントするためのスコアを割り当てます。^[6]一般に、異なる置換マトリックスは、異なる程度に分岐した配列間の類似性を検出するために調整されます。単一のマトリックスは、比較的広範囲の進化的変化に対してかなり効率的である可能性があります。^[6] BLOSUM-62 マトリックスは、弱いタンパク質類似性を検出するのに最適な置換マトリックスの 1 つです。^[6]数値の高い BLOSUM マトリックスは、密接に関連する配列を比較するために設計され、数値の低い BLOSUM マトリックスは、遠く離れた関連する配列を比較するために設計されています。たとえば、BLOSUM-80 は、配列がより類似しているアラインメントに使用され、BLOSUM-45 は、互いに分岐したアラインメントに使用されます。^[6]特に長くて弱いアラインメントの場合、BLOSUM-45 マトリックスが最良の結果をもたらす可能性があります。短いアラインメントは、BLOSUM-62 よりも「相対エントロピー」が高いマトリックスを使用すると、より簡単に検出されます。 BLOSUMシリーズには、最短クエリに適した相対エントロピーを持つ行列は含まれていません。^[6]

DNA複製の際、細胞の複製機構はDNAを複製する際に2種類のエラーを起こしやすい。これらの2つの複製エラーは、DNA鎖からの単一DNA塩基の挿入と削除（インデル）である。^[7] インデルはDNA鎖に突然変異を引き起こし、標的タンパク質の不活性化または過剰活性化につながる可能性があり、深刻な生物学的影響を及ぼす可能性がある。例えば、コード配列に1つまたは2つのヌクレオチドのインデルが発生すると、読み取りフレームがシフトするか、フレームシフト変異が発生し、タンパク質が不活性化される可能性がある。^{[7]インデルの生物学的影響は有害であることが多く、}がんなどの病理と頻繁に関連付けられている。ただし、すべてのインデルがフレームシフト変異であるわけではない。インデルが3ヌクレオチドで発生すると、タンパク質配列が拡張され、タンパク質機能にも影響を及ぼす可能性がある。^[7]

これは最も単純なタイプのギャップペナルティです。長さに関係なく、すべてのギャップに固定の負のスコアが与えられます。^{[3] [8]}これにより、アルゴリズムはより少ない、より大きなギャップを作成し、より大きな連続セクションを残すようになります。

ATTGACCTGA
|| |||||
AT---CCTGA

2 つの短い DNA 配列を並べます。「-」は 1 塩基対のギャップを表します。各一致が 1 ポイントで、ギャップ全体が -1 の場合、合計スコアは 7 − 1 = 6 になります。

一定のギャップペナルティと比較して、線形ギャップペナルティはギャップ内の各挿入/削除の長さ（L）を考慮に入れます。したがって、挿入/削除された各要素のペナルティがBで、ギャップの長さがLの場合、合計ギャップペナルティは2つのBLの積になります。^[9]この方法は、ギャップが短いほど有利であり、ギャップが増えるごとに合計スコアが減少します。

ATTGACCTGA
|| |||||
AT---CCTGA

一定のギャップペナルティとは異なり、ギャップのサイズが考慮されます。スコアが 1 でギャップごとに -1 の一致の場合、ここでのスコアは (7 − 3 = 4) です。

最も広く使用されているギャップペナルティ関数は、アフィンギャップペナルティです。アフィンギャップペナルティは、定数ギャップペナルティと線形ギャップペナルティの両方の要素を組み合わせて、 という形式になります。これにより、新しい用語が導入され、A はギャップオープニングペナルティ、B はギャップエクステンションペナルティ、L はギャップの長さと呼ばれます。ギャップオープニングとは、任意の長さのギャップを開くために必要なコストを指し、ギャップエクステンションとは、既存のギャップの長さを 1 延長するためのコストを指します。^[10] A と B の値は目的によって異なるため、多くの場合、値 A と B が何であるべきかは不明瞭です。一般に、関連性の高い一致を見つけることが目的の場合 (例: ゲノムシーケンシング中のベクター配列の削除)、ギャップオープニングを減らすために、より高いギャップペナルティを使用する必要があります。一方、より遠い一致を見つけることが目的の場合は、ギャップペナルティを低くする必要があります。^[9] A と B の関係もギャップサイズに影響します。ギャップのサイズが重要な場合は、小さい A と大きい B (ギャップを延長するコストが高い) を使用し、その逆も同様です。比率 A/B のみが重要です。両方に同じ正の定数を掛けると、すべてのペナルティが:だけ増加しますが、異なるアライメント間の相対的なペナルティは変化しません。 ${\displaystyle A+B\cdot (L-1)}$${\displaystyle k}$${\displaystyle k}$${\displaystyle kA+kB(L-1)=k(A+B(L-1))}$

アフィンギャップペナルティを使用するには、ギャップを開くことと拡張することの両方に対して固定のペナルティ値を割り当てる必要があります。これは生物学的な文脈で使用するには厳しすぎる可能性があります。^[11]

対数ギャップは の形をとり、研究によりインデルサイズの分布がべき乗法則に従うことが示されたため提案されました。^[12]アフィンギャップの使用に関するもう1つの問題は、より短いギャップを持つ配列のアラインメントが好まれることです。対数ギャップペナルティは、長いギャップが望ましいようにアフィンギャップを修正するために考案されました。^[11]しかし、これとは対照的に、対数モデルを使用すると、アフィンモデルと比較してアラインメントの品質が低下することが判明しました。^[12]${\displaystyle G(L)=A+C\ln L}$

プロファイル-プロファイルアラインメントアルゴリズムは、アラインメント精度を向上させながらタンパク質相同性関係を検出するための強力なツールです。^[13]プロファイル-プロファイルアラインメントは、PSI-BLAST検索によって生成された多重配列アラインメントからの統計的インデル頻度プロファイルに基づいています。^[13]置換マトリックスを使用してアミノ酸ペアの類似性を測定するのではなく、プロファイル-プロファイルアラインメント法では、プロファイルベクトルペアの類似性を測定するためにプロファイルベースのスコアリング関数が必要です。^[13]プロファイル-プロファイルアラインメントでは、ギャップペナルティ関数が使用されます。ギャップ情報は通常、アラインメントする配列に固有のインデル頻度プロファイルの形式で使用されます。ClustalWとMAFFTは、多重配列アラインメントにこの種のギャップペナルティ決定を採用しました。^[13]このモデルを使用すると、特に配列同一性の低いタンパク質の場合、アラインメント精度を向上させることができます。一部のプロファイル-プロファイルアラインメントアルゴリズムでは、スコアリング関数の1つの項として二次構造情報も実行され、アラインメント精度が向上します。^[13]

計算生物学におけるアライメントの使用には、さまざまな長さの配列が含まれることがよくあります。既知の入力サイズで効率的に実行されるモデルを選択することが重要です。アルゴリズムの実行にかかる時間は、時間計算量と呼ばれます。

ギャップを扱う際には、いくつかの課題があります。一般的なアルゴリズムを使用する場合、ギャップペナルティ関数の形式に関する理論的根拠はほとんどないようです。^[14]その結果、どのようなアラインメント状況でも、ギャップの配置は経験的に決定する必要があります。^[14]また、アフィンギャップペナルティなどのペアワイズアラインメントギャップペナルティは、ギャップ領域では特定の残基タイプが好まれるという証拠があるにもかかわらず、挿入または削除されたフラグメントまたは切断された末端のアミノ酸タイプとは無関係に実装されることがよくあります。^[14]最後に、配列のアラインメントは対応する構造のアラインメントを意味しますが、タンパク質のギャップの構造的特徴とそれに対応する配列の関係は不完全にしかわかっていません。このため、ギャップペナルティに構造情報を組み込むことは困難です。^[14]一部のアルゴリズムは、予測された構造情報または実際の構造情報を使用してギャップの配置をバイアスします。ただし、構造がわかっている配列は少数であり、ほとんどのアラインメントの問題には、未知の二次構造および三次構造の配列が含まれます。^[14]

• Taylor WR、Munro RE (1997)。「複数シーケンススレッド：条件付きギャップ配置」。Fold  Des . 2 ( 4): S33-9。doi : 10.1016 /S1359-0278(97)00061-8。PMID 9269566。
•  Taylor WR (1996)。「プロファイルアライメントのための非局所ギャップペナルティ」。Bull Math Biol。58 ( 1 ): 1–18。doi : 10.1007 /BF02458279。PMID 8819751。S2CID 189884646  。
• Vingron M、Waterman MS (1994)。「配列アラインメントとペナルティの選択。概念、ケーススタディ、および影響のレビュー」。J Mol Biol . 235 (1): 1–12。doi : 10.1016 /S0022-2836(05)80006-3。PMID 8289235  。
• Panjukov VV (1993). 「安定したアラインメントを見つける: 類似性と距離」Comput Appl Biosci . 9 (3): 285–90. doi :10.1093/bioinformatics/9.3.285. PMID  8324629.
• Alexandrov NN (1992). 「コンセンサスマトリックスによるローカルマルチプルアラインメント」Comput Appl Biosci . 8 (4): 339–45. doi :10.1093/bioinformatics/8.4.339. PMID  1498689.
• Hein J (1989)。「系統発生が与えられた場合に、任意の数の相同配列の祖先配列を同時に整列および再構築する新しい方法」。Mol Biol Evol . 6 (6): 649–68。doi : 10.1093 /oxfordjournals.molbev.a040577。PMID  2488477 。
• Henneke CM (1989)。「二次構造情報を使用し、オプションで機能的に重要な部位にアラインメントをキーイングする相同タンパク質の多重配列アラインメントアルゴリズム」。Comput Appl Biosci . 5 (2): 141–50. doi :10.1093/bioinformatics/5.2.141. PMID  2751764。
• Reich JG、Drabsch H、Daumler A (1984)。「DNA配列の類似性の統計的評価について」。Nucleic Acids Res . 12 (13): 5529–43. doi :10.1093/nar/12.13.5529. PMC  318937 . PMID  6462914。