奈良女子大集中講義バイオインフォマティクス (7) 進化系統樹阿久津達也京都大学化学研究所バイオインフォマティクスセンター講義予定 • 9月5日 – – – – 分子生物学概観分子生物学データベース配列アラインメント実習１（データベース検索と配列アラインメント） • 9月6日 – – – – モチーフ発見隠れマルコフモデルカーネル法進化系統樹推定 • 9月7日 – – – – タンパク質立体構造予測相互作用推定スケールフリーネットワーク実習２（構造予測）進化系統樹推定 • 系統樹の個数 • 距離行列法 – UPGMA法 – 近隣結合法 • 最節約法 • 進化の確率モデル – 最尤法進化系統樹 • 種間（もしくは遺伝子間）の進化の関係を表す木 • 以前は形態的特徴をもとに構成 • 現在は配列情報をもとに構成（イメージ図：実際の進化とは直接、関係無い）有根系統樹と無根系統樹 • • • • • • • 節点（頂点）：木の葉、もしくは、枝分かれ部分枝（辺）：種の親子関係を表す枝長：進化に要した時間に対応葉：現在の種に相当する節点根：進化の起点にあたる節点有根系統樹（根つき木）：根のある系統樹（下図の左）無根系統樹（根なし木）：根のない系統樹（下図の右）系統樹の同型性 • 同型な系統樹：本質的に同じつながり方（グラフとして同型）をした系統樹 • (a)と(b)：同型 (a)と(c)：非同型 • (d)と(e)：同型 (d)と(f)：非同型系統樹の個数 • 葉の個数と節点の個数の関係（葉の個数＝ n） – 有根系統樹： 2n-1 個の節点、 2n-2 本の枝 – 無根系統樹： 2n-2 個の節点、 2n-3 本の枝 • 無根系統樹と有根系統樹の関係 – 値は無根系統樹の任意の枝に設定可能 ⇒ 有根系統樹の個数＝(2n-3)×無根系統樹の個数 – 枝が 2n-3 本の無根系統樹に1本の枝を追加 ⇒ 2n-3 種類の異なる無根系統樹 #葉 #枝（無根系統樹） #無根系統樹 #有値系統樹 3 3 1 3 4 5 3 3×5 5 7 3×5 3×5×7 6 9 3×5×7 3×5×7×9 … … … … n 2n-3 (2n-5)!! (2n-3)!! 系統樹の個数（例） • • 値は無根系統樹の任意の枝に設定可能 ⇒ 有根系統樹の個数＝(2n-3)×無根系統樹の個数枝が 2n-3 本の無根系統樹に1本の枝を追加 ⇒ 2n-3 種類の異なる無根系統樹距離行列法 • 最初に、種（葉）の間の距離をすべて計算 • その距離をもとに系統樹を推定 • クラスタリング手法の一種 • UPGMA法 – 距離最短のクラスタをみつけては結合 • 近隣結合法 – 近隣となる葉をみつけては結合 UPGMA法 (Unweighted pair group method using arithmetic averages) • アルゴリズム – 各配列のみからなるクラスタを作成 – クラスタが２個になるまで以下を繰り返す • クラスタ間距離が最小のクラスタどうしを併合 • 新しくできたクラスタと他のクラスタ間の距離を計算 • クラスタ間距離 1 Dkl  dij  | Ck || Cl | iCk , jCl • 距離の性質 Dil | Ci | Djl | C j | Dkl  | Ci |  | C j | UPGMA法（例1） C6  C4  C5  {4,5}  C7  C1  C2  {1,2}  C8  C7  C3  {1,2,3}  C9  C6  C8  {1,2,3,4,5} 分子時計 • 分子時計＝進化速度一定性の仮定 • 枝長＝分子時計により刻まれた時間 • 分子時計仮説が成立  「任意の葉までの枝長の和が等しい」が任意節点について成立 ⇒UPGMA法は系統樹を正しく再構成以下の例で、(a) は仮説を満たさないが、(b)は満たす近隣結合法（１） • UPGMA法では以下の例(a)で、2と3が最初に選ばれたため、正しい系統樹を再構成できなかった • 最初に、3と4、もしくは、1と2が選ばれれば良い • つまり、兄弟関係（近隣関係）にある葉が選ばれれば良い • 近隣結合法では（距離が加法性を満たすという仮定のもとで）常に近隣関係にある葉を選ぶ近隣結合法（2） • 近隣結合法 – 距離が加法性を満たせば系統樹を正しく再構成 – ただし、計算されるのは無根系統樹 • 加法性：節点間の距離＝節点間を結ぶパスの枝長の和アウトグループ • 近隣結合法：無根系統樹しか計算されない • 無根系統樹における根の決定法 – 最も長い葉の間の中点を根とする – 対象とする種と離れていることが明らかな種（アウトグループ）を追加して系統樹を作成し、アウトグループに接続する接点を根とする最節約法（１） • 最小置換で各配列を生成する系統樹を計算 • ２種類の探索が必要 – 系統樹の形状（トポロジー) ⇒ 難しい – 内部節点への配列の割り当て ⇒ 動的計画法で計算可能最節約法（２） • Sk(a) : 節点 k に塩基 a を割り当てた時のコスト • S(a,b) : a を b に置換するためのコスト • 動的計画法により葉から根という順で Sk(a) を計算 • 配列割り当ては各位置ごとに独立に計算可能 k が内部節点の場合（i,j は k の子節点） Sk (a)  min(Si (b)  S (a, b))  min(S j (b)  S (a, b)) b k が葉の場合  0 if a  sk [1] Sk (a)     otherwise b 最節約法（３） Sk (a)  min(Si (b)  S (a, b))  min(S j (b)  S (a, b)) b b 進化の確率モデル • P(b|a,t) : 長さ t の枝をたどることにより塩基 a が塩基 b に置換される確率 • P(y|x,t) : 長さ t の枝をたどることにより配列 x が配列 y に置換される確率 P( y | x, t )  P( yu | xu , t ) u 置換行列（置換確率行列）  P(A | A, t )   P(A | C, t ) S (t )   P(A | G, t )   P(A | T, t ) 乗法性 P(C | A, t ) P(C | C, t ) P(C | G, t ) P(C | T, t ) P(G | A, t ) P(G | C, t ) P(G | G, t ) P(G | T, t ) S (t )S (s)  S (t  s) P(T | A, t )   P(T | C, t )  P(T | G, t )   P(T | T, t )  Jukes-Cantor行列（１） • 置換速度行列を R とし、 S (t )  I  Rt を仮定 • S(t) の乗法性より S (t  t )  S (t )  S (t )S (t )  S (t ) • よって  S (t )(I  Rt )  S (t )  S (t )Rt dS(t )  S (t )R dt • A,C,G,T が対等であるとして • 対称性より • よって     1  3   1  3      R   1  3       1  3     r (t )   s(t ) S (t )   s(t )   s(t ) s(t ) r (t ) s(t ) s(t ) s(t ) s(t ) r (t ) s(t ) dr(t ) ds(t )  3 r(t )  3 s(t )   r(t )  s(t ) dt dt s(t )   s(t )  s(t )   r (t )  Jukes-Cantor行列（２）     1  3  r (t )    1  3       s(t ) R S (t )      1  3  s(t )      1  3     s(t ) を dS(t )  S (t )R dt s(t ) r (t ) s(t ) s(t ) s(t ) s(t ) r (t ) s(t ) s(t )   s(t )  s(t )   r (t )  に代入して、 dr(t ) ds(t )  3 r(t )  3 s(t )   r(t )  s(t ) dt dt これを解いて r(t)  14 (1 3e4 t ) s(t)  14 (1 e4 t ) この S(t) が Jukes-Cantor行列 r(t )  s(t )  14 if t   は十分時間が経つと A,C,G,T の割合いが等しくなることを意味する Jukes-Cantor行列の応用例 • TATAT(=x)が t 時間後にTTAAA(=y)に置換する確率は P(T | A, t )  P(A | T,t )  14 (1  e4 t ) P(T | T,t )  P(A | A, t )  14 (1  3e4 t ) より 1 P( y | x, t )  5 (1 3e4 t )2 (1 e4 t )3 4 最尤法による系統樹推定 • 系統樹の尤度（確率） P(s1,, sn | T , t )   P(s 2 n1 sn1 ,, s2 n1 • 配列 s1,…,sn に対し、尤度最大の系統樹のトポロジー T と、枝長 ti を計算 – ただし、p(i) は i の親節点 • この計算は難しく、様々な手法が提案されている 2 n 2 )  P(si | s p(i ) , ti ) i 1 尤度計算の例（１） • 1塩基あたりの尤度 P( xu1 , xu2 | T , t1, t2 )  qa P( xu1 | a, t1 )P( xu2 | a, t2 ) a • 配列全体の尤度 N P( x1, x2 | T , t1, t2 )   P( xu1 , xu2 | T , t1, t2 ) i 1 尤度計算の例（2） • CGのみからなる配列 CCGGCCGCGCG CGGGCCGGCCG • n1個は同じで n2個は変化（この例では、n1=8, n2=3） P(C, C | T , t1, t2 )  qCrt1 rt2  qG st1 st2  qA st1 st2  qT st1 st2  14 (rt1 rt2  3st1 st2 )  161 (1  3e-4 (t1 t2 ) ) P(C, G | T , t1, t2 )  14 (rt1 st2  st1 rt2  2st1 st2 )  161 (1  e-4 (t1 t2 ) ) よって、系統樹全体の尤度は、 P( x , x | T , t1, t2 )  1 2 1 16n1 n2 (1 3e-4 (t1 t2 ) )n1 (1 e-4 (t1 t2 ) )n2 尤度は、t1+t2 が一定なら変わらないことに注意 ⇒ 根の位置の任意性まとめ • 系統樹の個数 • 距離行列法 – UPGMA法：最小距離のクラスタを結合 – 近隣結合法：近隣の節点を結合 • 最節約法 – 置換コストが最小の系統樹を計算 • 進化の確率モデル – Jukes-Cantor行列を用いて配列間の置換確率を計算 – 最尤法：確率が最大となる系統樹を推定 • 参考文献 – 阿久津：バイオインフォマティクスの数理とアルゴリズム、共立出版、2007