分子生物情報学(2) 配列のマルチプルアライメント法

Presentation on theme: "分子生物情報学(2) 配列のマルチプルアライメント法"— Presentation transcript:

1 分子生物情報学(2) 配列のマルチプルアライメント法
阿久津　達也 京都大学　化学研究所 バイオインフォマティクスセンター

2 内容 ペアワイズアライメントの復習 マルチプルアライメント 多次元DP プログレッシブアライメント モチーフ発見 局所マルチプルアライメント

3 マルチプルアライメント：意味 ３本以上の配列が与えられた時、全ての配列の長さが同じになるようにギャップを挿入
進化的、構造的に相同な残基（塩基）ができるだけ同じカラムに並ぶようにする 通常はスコアを用いて、最適化問題として定式化 理想的なアライメント 同一残基から派生した残基が同一カラムに並ぶ 構造的に重なり合う残基が同一カラムに並ぶ ⇒構造的に重なり合わない場所を無理に重ね合わせるのは、あまり意味がない

4 マルチプルアライメント：定式化 S(mi) = -∑cia log pia （cia= i列におけるaの出現回数,
３本以上の配列が与えられた時、長さが同じで、かつ、スコアが最適となるように各配列にギャップを挿入したもの スコアづけ　（全体スコアは基本的に各列のスコアの和:∑S(mi)） 最小エントロピースコア S(mi) = -∑cia log pia　　　（cia= i列におけるaの出現回数, 　　　　 pia = i列におけるaの生起確率） SPスコア(Sum-of-Pairs) S(mi)=∑k＜ｌ s(mik,mil) （mik = i列, k行目の文字）

5 SP(Sum of Pairs)スコア S(mi)=∑k＜ｌ s(mik,mil) 問題点 mik = i列, k行目の文字
確率的な正当性が無い 同一カラムに a,b,c が並んだ場合、log(pabc/qaqbqc) とすべきだが、SPスコアでは　 log(pab/qaqb)+ log(pbc/qbqc)+ log(pac/qaqc)

6 多次元DPによる マルチプルアライメント N個の配列に対するマルチプルアライメント 例：N=3
N次元DPによりO(2NnN)時間（各配列の長さはO(n)を仮定） 例：N=3

7 マルチプルアライメントの計算手法 分枝限定法 シミュレーテッドアニーリング 遺伝的アルゴリズム 逐次改善法 HMMによるアライメント
１０配列程度なら最適解が計算可能 シミュレーテッドアニーリング 遺伝的アルゴリズム 逐次改善法 HMMによるアライメント プログレッシブアライメント CLUSTAL-W（最も広く利用されているソフト）で採用 逐次改善法との組み合わせが、より有効

8 実用的マルチプルアライメント法 ヒューリスティックアルゴリズムの開発 プログレッシブアライメント 逐次改善法 N次元DPは（N=4ですら）
　　　非実用的 一般にはNP困難 プログレッシブアライメント 近隣結合法などを用いて　案内木を作る 類似度が高い節点から低い節点へという順番で、配列対配列、配列対プロファイル、プロファイル対プロファイルのアラインメントを順次計算 逐次改善法 「配列を一本取り除いては、アラインメントしなおす」を繰り返す

9 プログレッシブアライメント

10 プロファイル-プロファイル・アライメント
各列を１文字のように扱うことにより、DPにより計算

11 逐次改善法 「配列を一本取り除いては、アラインメントしなおす」を繰り返す

12 モチーフ発見 モチーフ :共通の性質を持つ遺伝子などに現れる共通の文字列パターン 決定的表現法 確率的表現法
正規表現などを用いる（例：　A-x(1,3)-[CG]） 一般にNP困難。学習理論において数多くの研究 正例のみならず、 　負例が与えられることが多い 確率的表現法 重み行列（プロファイル） Σ×[1…L] から実数への関数 HMM (Hidden Markov Models)

13 局所マルチプルアライメント (Local Multiple Alignment)
複数配列と長さLが与えられた時、スコア最大となるように各配列から長さLの部分列を抽出 モチーフ（共通の性質を持つ遺伝子などに共通の部分パターン）抽出などに有用

14 相対エントロピースコアのもとでの 局所マルチプルアライメント
相対エントロピースコアの定義 fj(a): （モチーフ領域の）j列目におけるaの出現頻度 p(a): aの出現頻度（事前確率） L: モチーフ領域の長さ 実用的アルゴリズム Gibbsサンプリング, EM NP困難

15 相対エントロピースコア L=7 f1(A)=1, f1(C)=f1(G)=f1(T)=0
f2(A)=2/3, f2(T)=1/3, f2(C)=f2(G)=0, … p(A)=p(C )=p(G)=p(T)=1/4

16 Gibbs サンプリング 各配列xjからランダムに部分配列tjを選ぶ 1個の配列xiをランダムに選ぶ
xiの部分列ti’を　　　　 に比例する確率で選ぶ ti をti’ でおきかえる ステップ2-4を十分な回数だけ繰り返す ( ti[j]: 部分列ti のj列目の文字 )

17 講義のまとめ(配列アライメント2) 配列のマルチプルアライメント法 多次元DP プログレッシブアライメント モチーフ発見
局所マルチプルアライメント 参考文献 阿久津、浅井、矢田　訳：　バイオインフォマティクス －確率モデルによる遺伝子配列解析―、医学出版、2001