Edited at

バイオインフォマティクス -ゲノム配列から機能解析へ- 第3章:対にした配列のアラインメント

More than 3 years have passed since last update.

これはバイオインフォマティクス ゲノム配列から機能解析へ 第2版輪読会の記録です。

目次はこちらです。


3.1 配列アラインメントとは?

配列アラインメントとは,DNAもしくはタンパク質配列中で同じ並び方をしている文字列や配列パターンを探すこと


比較配列数による違い



  • ペアワイズ配列アラインメント


    • 2配列間の比較




  • 多重配列アラインメント


    • 3本以上の配列間の比較




比較配列長による違い



  • 大域的アラインメント


    • 配列全体にわたる比較

    • よく似ていて,大体同じ長さの配列の比較に適している

    • Needleman-Wunschアルゴリズム




  • 局所的アラインメント


    • 一致密度の高い配列領域の比較

    • ある部分で似ているが他の部分では似ていない配列や,長さの異なる配列の比較に適している

    • Smith-Watermanアルゴリズム




3.2 配列アラインメントは機能や構造や進化的情報を明らかにする

非常によく類似した配列はきわめてよく似た機能を持つ


例えば,DNA分子なら同じ調整機能であったり,タンパク質ならよく似た生化学的機能と立体構造であったりする.


異種間で配列が類似するとき,進化的に同じ起源を持つ可能性があり,2つの配列は相同である(homologous)という


3.3 ペアワイズ配列アラインメントには3つの主要な方法がある

ペアワイズ配列アラインメントは,以下の方法を用いて行われる.

- ドットマトリックス解析

- ダイナミックプログラミング(DP)アルゴリズム

- ワードもしくはk-タプル法


3.3.1 ドットマトリックス解析

GibbsとMcIntyre(1970)によって発表


比較する配列を二次元の格子の縦横に並べ,一致している文字のペアを黒く塗った,グラフィカルな表示法

対応する部分は,連続する対角線として表示される

引用元: バイオインフォマティクス基礎講座 配列解析



利点



  • 2配列間の残基についてすべての可能な一致がわかる


    • ドットマトリックスに斜め線として現れる一致の長い連続した領域を調べて,最も優位な一致を識別する選択の余地を残している




  • 配列の繰り返しを見出す


    • DNAおよびタンパク質配列中の順方向や逆方向の反復配列を見つける



  • 単一の配列記号の繰り返しを見出す



3.3.2 DPアルゴリズム


アラインメント問題は,有向グラフの最適経路問題と等価

有効グラフの最適経路問題は動的計画法で解ける

引用元: バイオインフォマティクス基礎講座 配列解析


経路のコストとして,各塩基(アミノ酸)のオッズスコアが使われる.

オッズスコアとは,タンパク質中のアミノ酸の出現頻度を前提として,アミノ酸置換が偶然怒る回数に対して,類縁のあるタナパク室中でその置換が起こる割合


3.3.3 ワードとk-タプル法


初めに,同一の短い配列(ワードやk-タプルと呼ばれる)を探し,ダイナミックプログラミング法でこれらのワードをアラインメントに連結していくことで,2つの配列を非常に高速にアラインメントする.