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

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

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

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

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

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

系統樹の個数 葉の個数と節点の個数の関係（葉の個数 ＝ 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)!!

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

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

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

UPGMA法（例1）

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

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

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

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

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

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

最節約法（３）

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

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

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

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

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

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

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

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