Aritalab:Lecture/Bioinformatics/MultipleAlignment

Latest revision as of 09:44, 19 December 2011

[edit] 多重アライメント

[edit] 計算の意義

多重アライメントはふつう進化的に同一のグループに属するアミノ酸配列集合に対しておこない、機能や構造の違いや進化を明らかにするために用います。構造や機能を担ったアミノ酸ができるかぎり多く揃うようなアライメント結果が理想と考えられています。

配列 2 本を比較するアライメントは O( n² ) 時間でおこなえ、そのスコアはギャップやミスマッチの数によって決まりました。配列が m 本ある場合、m (m − 1) / 2 通りの組み合わせのスコアの総和で評価します。この評価法はペア総和型スコア　(sum of pairs scoring) と呼ばれ、ほとんどの多重アライメントアルゴリズムで利用されています。

さて、配列 m 本を m 次元動的計画法でアライメントすると O( 2^m n^m ) 時間のアルゴリズムになります。（ 2次元と3次元の場合で確かめてみてください。各セルの値を決めるのに (2^m - 1) 個の値を比較します。）これは m が 4 以上になると普通のPCではとても実行できません。ペア総和スコアの最適値を求める問題は、NP-完全に属することも示されています。実際には 100 本を超える配列の多重アライメントを計算する場合も少なくないため、簡単な枝刈り (branch-and-bounding) や分割統治法 (divide-and-conquering) ではとても対応できません。遺伝的アルゴリズムやシミュレーテッドアニーリングも提案されてはいますが、いずれも実用ではありません^[1]。現在は以下の二方法を組み合わせるのが主流です。

• 累進アライメント
• 逐次改善

[edit] 累進アライメント

"累進" とは英語でいうとプログレッシブ (progressive) です。以下のステップで多重アライメントを作成します。

1. 案内木 (guide tree) と呼ばれる配列の系統樹を作成
2. 系統樹の葉にちかい接点から（つまり最も似ている配列同士から）順次、上方向に配列をアライン
3. 最終的に系統樹の根に対応する部分のアライメント結果を返す

各接点におけるアライメント結果をそれより上流の接点で変更しなければ、接点のたびに少なくとも一つの配列を統合できるので O ( m n² ) 時間で多重アライメントが求まります。

[edit] 案内木の作成

配列 m 本の系統関係を推定するのに多重アライメントをおこなうので、案内木を作成する作業はいわば鶏と卵の関係にあります。 配列どうしの詳細な比較は時間がかかるので、通常は k-mer と呼ぶ連続する kアミノ酸の続きがどの程度保存されているか、ミスマッチを許した文字列検索アルゴリズムによる配列類似性のスコアを元に、近隣結合法 (NJ: Neighbor joining) や非加重結合法（UPGMA: Unweighted Pair Group Method with Arithmetic mean) を用いて系統樹を作成します。

こうして初期に作成した案內木はたいてい不正確なので、多重アライメントをおこなった後に再度、アライメント結果を元に案内木を修正します。修正した木をもとに多重アライメントをおこない、このプロセスは変更点がなくなるまで（収束するまで）繰り返すことができます。

[edit] プロファイルアライメント

案內木をたどるときは、配列の集合をあたかも 1 本の配列のように扱ってアライメントを行います。配列プロファイルを用いたアライメントを、プロファイルアライメントと呼びます。しかし、プロファイル同士の比較方式は多重アライメントの精度にはあまり貢献しないようです。（つまり、案內木の作成とその修正がずっと重要。）

[edit] 多重アライメント向けのスコア改良

多くの優れたソフトウェアは、よりよいアライメント結果を求めるために様々な例外スコアを設けています。そのうち幾つかを紹介します。

配列の重み付け

極端な例として m 本中にほとんど同じ配列がたくさん含まれて、少数の異なる配列がある場合を考えましょう。通常のペア総和型スコアでは、近い配列も遠い配列も均等に評価してしまうため、少数の異なる配列のアライメント精度が過小評価されてしまいます。そこで、もし類似の配列が数多く含まれる場合は、相対的にそれらの配列のアライメントスコアを下げる処理をおこないます。

ギャップペナルティの変更

多くの配列が同一位置にギャップを持つ場合、これらは進化的に単一のイベントによって生じ、それが多くの配列にコピーされたと考えます。したがって、ギャップペナルティを単に本数分足し合わせるのではなく、より少ない値に設定する必要が生じます。この他にも、親水性でループ領域に多いアミノ酸領域はギャップペナルティを下げる等の処理も行われます。

アライメント整合性

累進法では一番近いアミノ酸配列どうしからアライメントしていきますが、最も近い 2 本ではギャップ位置に複数の選択肢が生じる場合があります。このとき、進化的に遠い配列を参照して保存度をみることにより、系統樹に整合するギャップ位置を決められます。

[edit] 逐次改善

累進法では初期のアライメント結果が修正されないまま、案內木の根元に到達するまで使われてしまいます。結果的にうまく揃わない配列が生じえます。逐次改善法では、配列を 1 本ずつ取り除き、残りの配列からなるプロファイルと比較をやり直します。

[edit] ツール、ソフトウェア

ナショナルバイオデータベースセンターによるツールの紹介は こちら。 国内で開発され大変精度の高いソフトとして、MAFFT を薦めています。

参考

1. ↑ ただし、隠れマルコフモデルを用いたアライメントは使われていると言ってよいかもしれません。