奈良女子大集中講義 バイオインフォマティクス (7) 進化系統樹

Presentation on theme: "奈良女子大集中講義 バイオインフォマティクス (7) 進化系統樹"— Presentation transcript:

1 奈良女子大集中講義 バイオインフォマティクス (7) 進化系統樹
阿久津　達也 京都大学　化学研究所 バイオインフォマティクスセンター

2 講義予定 9月5日 9月6日 9月7日 分子生物学概観 分子生物学データベース 配列アラインメント
実習１（データベース検索と配列アラインメント） 9月6日 モチーフ発見 隠れマルコフモデル カーネル法 進化系統樹推定 9月7日 タンパク質立体構造予測 相互作用推定 スケールフリーネットワーク 実習２（構造予測）

3 進化系統樹推定 系統樹の個数 距離行列法 UPGMA法 近隣結合法 最節約法 進化の確率モデル 最尤法

4 進化系統樹 種間（もしくは遺伝子間）の進化の関係を表す木 以前は形態的特徴をもとに構成 現在は配列情報をもとに構成
（イメージ図：　実際の進化とは直接、関係無い）

5 有根系統樹と無根系統樹 節点（頂点）： 木の葉、もしくは、枝分かれ部分 枝（辺）： 種の親子関係を表す 枝長： 進化に要した時間に対応
節点（頂点）：　木の葉、もしくは、枝分かれ部分 枝（辺）：　種の親子関係を表す 枝長：　進化に要した時間に対応 葉：　現在の種に相当する節点 根：　進化の起点にあたる節点 有根系統樹（根つき木）：　根のある系統樹（下図の左） 無根系統樹（根なし木）：　根のない系統樹（下図の右）

6 系統樹の同型性 同型な系統樹：本質的に同じつながり方（グラフとして同型）をした系統樹 (a)と(b)：同型 (a)と(c)：非同型
(d)と(e)：同型 　　(d)と(f)：非同型

7 系統樹の個数 葉の個数と節点の個数の関係（葉の個数 ＝ n） 無根系統樹と有根系統樹の関係 n 2n-3
値は無根系統樹の任意の枝に設定可能 　　⇒　有根系統樹の個数＝(2n-3)×無根系統樹の個数 枝が 2n-3 本の無根系統樹に1本の枝を追加 　　⇒　2n-3 種類の異なる無根系統樹 #葉 #枝 （無根系統樹） #無根系統樹 #有値系統樹 3 1 4 5 3×5 7 3×5×7 6 9 3×5×7×9 … n 2n-3 (2n-5)!! (2n-3)!!

8 系統樹の個数（例） 値は無根系統樹の任意の枝に設定可能 ⇒ 有根系統樹の個数＝(2n-3)×無根系統樹の個数

9 距離行列法 最初に、種（葉）の間の距離をすべて計算 その距離をもとに系統樹を推定 クラスタリング手法の一種 UPGMA法 近隣結合法
距離最短のクラスタをみつけては結合 近隣結合法 近隣となる葉をみつけては結合

10 UPGMA法 (Unweighted pair group method using arithmetic averages)
アルゴリズム 各配列のみからなるクラスタを作成 クラスタが２個になるまで以下を繰り返す クラスタ間距離が最小のクラスタどうしを併合 新しくできたクラスタと他のクラスタ間の距離を計算 クラスタ間距離 距離の性質

11 UPGMA法（例1）

12 分子時計 分子時計＝進化速度一定性の仮定 枝長＝分子時計により刻まれた時間 分子時計仮説が成立 
分子時計仮説が成立　　 　「任意の葉までの枝長の和が等しい」が任意節点について成立 　⇒UPGMA法は系統樹を正しく再構成 　　　　　以下の例で、(a) は仮説を満たさないが、(b)は満たす

13 近隣結合法（１） UPGMA法では以下の例(a)で、2と3が最初に選ばれたため、正しい系統樹を再構成できなかった
最初に、3と4、もしくは、1と2が選ばれれば良い つまり、兄弟関係（近隣関係）にある葉が選ばれれば良い 近隣結合法では（距離が加法性を満たすという仮定のもとで） 常に近隣関係にある葉を選ぶ

14 近隣結合法（2） 近隣結合法 加法性： 節点間の距離 ＝ 節点間を結ぶパスの枝長の和 距離が加法性を満たせば系統樹を正しく再構成
ただし、計算されるのは無根系統樹 加法性：　節点間の距離　＝　節点間を結ぶパスの枝長の和

15 アウトグループ 近隣結合法： 無根系統樹しか計算されない 無根系統樹における根の決定法 最も長い葉の間の中点を根とする
近隣結合法：　無根系統樹しか計算されない 無根系統樹における根の決定法 最も長い葉の間の中点を根とする 対象とする種と離れていることが明らかな種（アウトグループ）を追加して系統樹を作成し、アウトグループに接続する接点を根とする

16 最節約法（１） 最小置換で各配列を生成する系統樹を計算 ２種類の探索が必要 系統樹の形状（トポロジー) ⇒ 難しい
系統樹の形状（トポロジー)　　⇒　難しい 内部節点への配列の割り当て　⇒　動的計画法で計算可能

17 最節約法（２） Sk(a) : 節点 k に塩基 a を割り当てた時のコスト S(a,b) : a を b に置換するためのコスト
配列割り当ては各位置ごとに独立に計算可能 k　が内部節点の場合（i,j は k の子節点） k　が葉の場合

18 最節約法（３）

19 進化の確率モデル P(b|a,t) : 長さ t の枝をたどることにより塩基 a が塩基 b に置換される確率
P(y|x,t) : 長さ t の枝をたどることにより配列 x が配列 y に置換される確率 置換行列　（置換確率行列） 乗法性

20 Jukes-Cantor行列（１） 置換速度行列を R とし、 を仮定 S(t) の乗法性より よって A,C,G,T が対等であるとして
対称性より

21 Jukes-Cantor行列（２） を に代入して、 これを解いて この S(t) が Jukes-Cantor行列
を　　　　　　　　　　　　に代入して、 これを解いて この S(t) が　Jukes-Cantor行列 　　　　　　　　　　　　　　　　　は十分時間が経つと A,C,G,T の割合いが等しくなることを意味する

22 Jukes-Cantor行列の応用例 TATAT(=x)が t 時間後にTTAAA(=y)に置換する確率は より

23 最尤法による系統樹推定 系統樹の尤度（確率） 配列 s1,…,sn に対し、尤度最大の系統樹のトポロジー T と、枝長 ti を計算
ただし、p(i) は i の親節点 この計算は難しく、様々な手法が提案されている

24 尤度計算の例（１） 1塩基あたりの尤度 配列全体の尤度

25 尤度計算の例（2） CGのみからなる配列 n1個は同じで n2個は変化 （この例では、n1=8, n2=3） よって、系統樹全体の尤度は、
尤度は、t1+t2 が一定なら変わらないことに注意　　 ⇒ 　根の位置の任意性

26 まとめ 系統樹の個数 距離行列法 最節約法 進化の確率モデル UPGMA法： 最小距離のクラスタを結合 近隣結合法： 近隣の節点を結合
近隣結合法：　近隣の節点を結合 最節約法 置換コストが最小の系統樹を計算 進化の確率モデル Jukes-Cantor行列を用いて配列間の置換確率を計算 最尤法：　確率が最大となる系統樹を推定 参考文献 阿久津：バイオインフォマティクスの数理とアルゴリズム、共立出版、2007