3S

ゲノム配列解析論Ⅰ 第5回

第5回 2019/5/20

講義内容

  • About MAFFT
  • Multiple sequence alignment methods
  • Dynamic Programming?
  • Heuristics (Progressive method, Iterative refinement method, Consistency)
  • 最近の話題
  • 可変スコアリングマトリクス
    • Vingron & Waterman (1994), Thompson et al. (1994) → Katoh & Standley (2016)
  • タンパク質の立体構造を考慮したアラインメントのための計算サービス
    • O’Sullivan et al (2004) → Rozewicki et al (2019)
  • 鎖状案内木の有用性
    • Barton & Sternberg (1987) → Boyce et al. (2014) ╳ Tan et al. (2015) ╳ Fox et al. (2016) ╳ Yamada et al. (2016)
  • 半自動アラインメント

About MAFFT

What is multiple sequence alignment(MSA)?

多重配列アラインメントは、「複数の配列を比較することで元となっている配列を予測する手法」のこと。

時間の経過とともに各塩基配列は独立に挿入・欠失・置換を受けるため、現在の配列を単純に比較しても元となった配列を推定することは難しい。

そこで、多くの場合「アラインメントをスコアリングし、最高のスコアのアラインメントを選択する」という手法を取る。スコアリングのモデルは様々なものが提案されているが、「(ギャップ開始ペナルティ) > (ギャップ伸長ペナルティ)」や「(ロイシン→イソロイシン) < (システイン→グリシン)」などの生物学的に意味のある（進化系統樹と整合性のある）関係性を入れたスコアが研究されている。

アラインメントという操作は適応範囲がかなり広く、進化系統樹解析、タンパク質やRNNの機能構造・二次構造予測、シークエンス時のコンセンサス配列決定、オーソログ・ホモログ識別などに用いられている。そのため、かなり研究が盛んな分野でもある。

加藤先生はMAFFTというアプリケーションを作成しており、かなり利用されている。

Multiple sequence alignment methods

今回の授業では、MAFFTの中で使われているアルゴリズムのうち、以下の3つの論文の内容をカバーする。

Dynamic Programming?

Pairwise sequence alignment

2本の配列を比較するのがペアワイズアラインメント。

基本的な考え方はDP。"Pairwise alignment score"を最大化するのが目的である。DP matrixを用いて効率的にスコアを最大化し、最後にback-trackする。計算量は DP matrix の面積に比例する。

Multiple sequence alignment

3本以上の時でも一応はできるが、計算量が多い上に厳密解を求めることはかなり難しい…というか厳密的な全ペアの最大化って何？

比較している現在の配列はそれぞれ独立ではなく木構造を取っていたため、\(\mathrm{SP} = \sum\mathrm{Pair\ alignment\ score}\) とするのはあまり使われていない。

主要なアルゴリズムとして、「累進法」と「反復改善法」が挙げられる。

累進法(Progressive Method)

  • Pairwise alignment を繰り返しながら更新し、最終的なアラインメトを得る手法。（ある子孫グループの各メンバーを別の子孫グループの各メンバーとペアワイズするイメージ。つまり、重み付けされたスコアを用いる。）
  • 高速に計算が可能
  • "Once a gap, always a gap"
入力配列の間の全通りの比較に基づいて距離行列(Distance matrix)と案内木(Tree)を計算する。この案内木にしたがってまず配列aと配列b、次に配列cと配列d、続いて配列グループcdとc、というような順番でグループ間アラインメントを繰り返す。
ここで、案内木を再構築してもう一度アラインメントを繰り返すと精度が向上する場合がある。

反復改善法(Iterative Algorithm)

  • 累進法などで得られたアラインメントを2つに分割し、それらのアラインメントから再び1つのアラインメントを計算する（ある評価関数の値が上昇したら更新）、ということを繰り返す手法
  • アラインメント中のエラーを取り除くことが可能
  • 進化的な距離を踏まえるため、系統樹の枝を切断する形でアラインメントを2つに分割する
  • 計算量は多いが、高精度。

FFT(fast Fourier transform)

MAFFTの中心的なアルゴリズムの一つにFFT(fast Fourier transform)がある。これは、フーリエ変換を用いて「相同性が明らかな領域」を高速に識別する手法のことである。

この手法を用いると、確実にマッチングさせるべき領域がわかるので、計算量が大幅に減る。定量的には、\(O(L^2)\) から \(O(L\log L)\) に減ることが知られている。

Embedding

FFTを使う上で、個々の配列を波として捉える必要がある。そこで、アミノ酸や塩基配列をベクトル表現する手法が提案されている。

  • アミノ酸 アミノ酸の特徴を極性と体積で表すことができる。
  • DNA 「A→i,G→1,C→-1,T→-i」のように複素数を用いることでベクトル表現することができる。

Consistency Criterion

「間違いを訂正する代わりに最初から間違えないようにしよう」という考え方。

通常はAとBのみを比較するが、Library extension という操作を行う。全ペアのアラインメントを計算するということ。

この手法には、「直接比較していない他の配列の情報も含めた配列の比較ができるので間違えにくいだろう」というアイデアが根底にある。単純な累進法よりも（ある評価基準のもとでは）良い結果を返すが、計算量が多くなってしまう。

より数学的に厳密的な手法を撮ったものがMSAProbsとか。これは重みをつけている。

PRANK

従来の累進法のおかしな点を指摘。例えば以下の左の図を考える。

まず、累進法で考えると、以下により合計 -3.5 となる。

  1. "A-T" と "AGT" の間のアラインメントにより、▼(-2)
  2. "A-T/AGT" と "A-T" の間のアラインメントにより、▽(-0.5)
  3. "A-T/AGT/A-T" と "ACT" の間のアラインメントにより、🔴(-1)

しかし、この進化系統樹が正しいとすると、進化の順序を考えると

  1. ③で、AT　と ACT　が分岐。2配列のアラインメントは、"A-T/ACT" のようになる。
  2. ②で、AT と AGT が分岐する。2配列のアラインメントは、"A-T/AGT" のようになる。

この２つのアラインメントを統合するとき、CとGには共通祖先が無い（置換によってCとGが分岐したのではない）ので同じカラムにCとGをアラインメントするのはおかしい。

そこで、PRANK というメソッドもあるが、PRANK is less prone to "over-alignment（合わせすぎ）"

最近の話題

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

詳しくは論文参照：A simple method to control over-alignment in the MAFFT multiple sequence alignment program

合わせすぎ問題に対応するためのもの。

スコア行列から定数 \(a\) を引くことでこの問題に対応した。DPの式を考えれば、こうなることは自明。（∵アラインメントを長くすることがペナルティ）

\(a\) の値も変化させるようにしており、配列（グループ）間の類似性にしたがって異なるスコア行列を用いるアイデアは一時期取られていたが、今では使われていない。

置換行列は通常「進化的に共通祖先を持つモデルと無関係なモデルの対数尤度比」で、定義される。

BLOSUM行列

配列の一致度が高いところでマルチプルアライメントをとり、特に保存性の高いところでのアミノ酸の変異を解析して求めたもの。

BLOSUM $x$ 行列の求め方
  • 既存の多くの配列のアラインメントを求めギャップ無しの領域(ブロック)を集める。
  • 残基が $x$% 以上一致しているものを同一クラスタに集める。
  • 同じ文字が $a$ と $b$ に変異する確率($a$ と $b$ が整列する確率)$p_{ab}=p_{ba}$ を求める。（2本の配列が進化的に関係があるとするモデル）
  • 文字 $a$ が現れる確率 $q_a$ を求める（2本の配列に関係がないとするモデル）
  • $s(a,b) = T\log\frac{p_{ab}}{q_aq_b}$ をスコアとする。（$T$ はスケーリング）

    • したがって、共通祖先を持つモデルでは、文字の同時確率　\(p_{a,b}\) が、進化的距離（何年前に分岐したか）によって異なるので、進化的距離に応じた置換行列を使うことが求められる。

    まとめ

    • ユーザ向け
    • 可変スコアリングマトリクスによって、全体的に類似度の高い配列の途中に、類似度の低い部分が見 つかった場合、そこを合わせないようになる。
    • → 合わせすぎ問題は緩和される。
      • 難点: 定量的評価はシミュレーションのみ。
    • 厳密に系統樹を考慮する方法 (PRANK、BAli-Phy) に比べて不足は残る。
    • 一方、弱い保存領域を特定する能力は、PRANKやBAli-Phyを上回る。
    • 開発者向け
    • ベンチマークの基準によって結果は全然異なる。特に MSAProbs • 適切な基準を設定することは、難しいけれども重要な課題。
    • 合わせすぎを防ぐには、他の方法も可能。
      • 専用マトリクス (Yamada & Tomii 2014, for remote homologs)?
      • ペアワイズアラインメントの座位ごとに、信頼性評価 (Hamada et al 2011)、以後マスク?

    ※ 配列の合わせすぎ問題はかなり深刻。「変な配列をどのように無視するか」が難しい。

    タンパク質の立体構造を考慮したアラインメントのための計算サービス

    立体構造の評価はかなり難しい。なぜなら、「もともと立体構造上の距離が近かったのだが構造が変わった。ところが配列部分は機能的に重要な役割を果たしていたため配列自身は保存されている」という可能性もあるから。

    そこで、タンパク質の立体構造の評価に関しては、「合わせるべきところ（立体構造上近いところ）を合わせられているか？？」のみを指標としている。

    タンパク質の構造を考慮する必要について

    タンパク質の立体構造を考慮した方がより信頼性の高いアラインメントが得られる。

    • タンパク質をコードする遺伝子に対する進化的制約
    • タンパク質の機能の保持 ~ 立体構造の保持が、配列の保存より直接的な制約として働く
    • したがって、配列上の類似性は見られなくなってしまった後も、立体構造上の類似性が 残っている場合が多い
    • 遠い関係にある配列の比較解析のために有用
    • 多重配列アラインメントへの適用
    • 3DCoffee (2004)
    • Promals3D (2008)

    鎖状案内木の有用性

    • ContTest (Fox et al. 2016) は再現する。
    • 確かに、鎖状案内木（ランダム案内木）がよい結果を与えることもある。（Simple chained guide trees give high-quality protein multiple sequence alignments）
    • ただし、k-mer距離に基づく案内木に比べて。
    • 全ペアDP (計算コスト高) に基づく案内木が望ましい。
    • 反復改善法や整合性の考慮など他の既知のテクニックによって、鎖状案内木より安定的に大アラインメントの正確さは向上する。
    • それらを適用可能にする必要。

    last-train

    ここまでは進化的に関係のある配列をアラインメントしていたが、ここでは進化的に関係がない配列を並べてコンセンサスアラインメントを行う。 普通にペアワイズアラインメントをしてパラメータを推測→アラインメントし直すを繰り返す。

    半自動アラインメント

    時間がなかったので省略された。

    hidden
    Table of Contents
    Published
    Last Updated
    Category
    ゲノム配列解析論Ⅰ
    Tags
    Contact
    Other contents
    • Home
    • Blog
    • Front-End
    • Kerasy
    • Python-Charmers
    • Translation-Gummy