ギャップペナルティ
Method of DNA analysis

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

アプリケーション

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

バイオインフォマティクスアプリケーション

グローバルアライメント

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

セミグローバルアライメント

セミグローバルアライメントは、大規模な配列内から特定の一致を見つけるために使用されます。例えば、DNA配列内のプロモーターを探す場合などが挙げられます。グローバルアライメントとは異なり、セミグローバルアライメントでは、片方または両方の配列にエンドギャップが存在しないことを前提としています。一方の配列1ではエンドギャップがペナルティの対象となり、配列2では対象としない場合、配列1内に配列2を含むアライメントが生成されます。

ローカルアライメント

文章
タンパク質配列アライメントの例

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

スコアリングマトリックス

文章
ブロサム-62マトリックス

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 の値は目的によって異なるため、適切な値が明確でないことがよくあります。一般に、関連性の高い一致を見つけることが目的の場合 (ゲノムシーケンス中にベクターシーケンスを削除するなど)、ギャップオープニングを減らすために、より高いギャップペナルティを使用する必要があります。一方、より遠い一致を見つけることが目的の場合は、ギャップペナルティを低くする必要があります。[9] A と B の関係もギャップのサイズに影響を及ぼします。ギャップのサイズが重要な場合は、小さい A と大きい B (ギャップを拡張するためのコストが高い) を使用し、その逆も同様です。比率 A/B のみが重要です。両方に同じ正の定数を掛けると、すべてのペナルティが:だけ増加しますが、異なるアライメント間の相対的なペナルティは変わりません。 A + B ⋅ ( L − 1 ) {\displaystyle A+B\cdot (L-1)} k {\displaystyle k} k {\displaystyle k} k A + k B ( L − 1 ) = k ( A + B ( L − 1 ) ) {\displaystyle kA+kB(L-1)=k(A+B(L-1))}

凹面

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

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

プロフィールベース

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

時間計算量の比較

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

さまざまなギャップペナルティモデルの時間計算量
タイプ 時間
一定のギャップペナルティ O(分)
アフィンギャップペナルティ O(分)
凹ギャップペナルティ O(mn lg(m+n))

課題

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

参考文献

  1. ^ ab 「用語集」。ロザリンド。ロザリンドチーム。2021年5月20日閲覧。
  2. ^ Carroll, Ridge, Clement, Snell, Hyrum , Perry, Mark, Quinn (2007年1月1日). 「ギャップオープンとギャップ伸長ペナルティの影響」. International Journal of Bioinformatics Research and Applications . 2014年9月9日閲覧。{{cite journal}}: CS1 maint: multiple names: authors list (link)
  3. ^ abc 「ギャップペナルティ」（PDF） . Algorithms for Molecular Biology . 2006年1月1日. オリジナル（PDF）から2013年6月26日にアーカイブ。 2014年9月13日閲覧。
  4. ^ Lesk, Arthur M (2013-07-26). 「バイオインフォマティクス」.ブリタニカ百科事典. 2014年9月12日閲覧。
  5. ^ Vingron, M.; Waterman, MS (1994). 「配列アライメントとペナルティ選択：概念、事例研究、そしてその影響のレビュー」. Journal of Molecular Biology . 235 (1): 1– 12. doi :10.1016/S0022-2836(05)80006-3. PMID  8289235.
  6. ^ abcdef 「BLAST置換マトリックス」NCBI . 2012年11月27日閲覧。
  7. ^ abc Garcia-Diaz, Miguel (2006). 「遺伝的グリッサンドのメカニズム：インデル変異の構造生物学」. Trends in Biochemical Sciences . 31 (4): 206– 214. doi :10.1016/j.tibs.2006.02.004. PMID  16545956.
  8. ^ 「用語集 - 一定ギャップペナルティ」ロザリンド、ロザリンドチーム、2014年8月12日。 2014年8月12日閲覧。
  9. ^ ab Hodgman C, French A, Westhead D (2009). BIOS Instant Notes in Bioinformatics . Garland Science. pp.  143– 144. ISBN 978-0203967249。
  10. ^ 「スコアリング行列とアフィンギャップペナルティを用いたグローバルアライメント」ロザリンド。ロザリンドチーム。2012年7月2日。 2014年9月12日閲覧。
  11. ^ ab Sung, Wing-Kin (2011).バイオインフォマティクスにおけるアルゴリズム：実践入門. CRC Press. pp.  42– 47. ISBN 978-1420070347。
  12. ^ ab Cartwright, Reed (2006-12-05). 「対数ギャップコストはアライメント精度を低下させる」BMC Bioinformatics . 7 : 527. doi : 10.1186/1471-2105-7-527 . PMC 1770940 . PMID  17147805. 
  13. ^ abcde Wang C, Yan RX, Wang XF, Si JN, Zhang Z (2011年10月12日). 「プロファイル-プロファイルアライメントにおける線形ギャップペナルティとプロファイルベースの可変ギャップペナルティの比較」Comput Biol Chem . 35 (5): 308– 318. doi :10.1016/j.compbiolchem.2011.07.006. PMID  22000802.
  14. ^ abcde Wrabl JO, Grishin NV (2004年1月1日). 「構造的に類似したタンパク質におけるギャップ：多重配列アライメントの改善に向けて」. Proteins . 54 (1): 71– 87. doi :10.1002/prot.10508. PMID  14705025. S2CID  20474119.

さらに読む

  • 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 .
Retrieved from "https://en.wikipedia.org/w/index.php?title=Gap_penalty&oldid=1305524143"