情報生命科学特別講義III （７）進化系統樹推定 阿久津　達也 京都大学　化学研究所 バイオインフォマティクスセンター

講義予定 第１回: 文字列マッチング 第２回： 文字列データ構造 第３回： たたみ込みとハッシュに基づくマッチング 第１回:　文字列マッチング 第２回：　文字列データ構造 第３回：　たたみ込みとハッシュに基づくマッチング 第４回：　近似文字列マッチング 第５回：　配列アラインメント 第６回：　配列解析 第７回：　進化系統樹推定 第８回：　木構造の比較：順序木 第９回：　木構造の比較：無順序木 第１０回：　文法圧縮 第１１回：　RNA二次構造予測 第１２回：　タンパク質立体構造の予測と比較 第１３回：　固定パラメータアルゴリズムと部分k木 第１４回：　グラフの比較と列挙 第１５回：　まとめ

進化系統樹

進化系統樹 種間（もしくは遺伝子間）の進化の関係を表す木 以前は形態的特徴をもとに構成 現在は配列情報をもとに構成

有根系統樹と無根系統樹 有根系統樹: 根（共通の祖先に対応）がある系統樹 無根系統樹: 根のない系統樹 いずれも葉にのみラベル（種に対応）がつく 有根系統樹 無根系統樹 系統樹を扱う際は、頂点でなく節点という用語を使う

進化系統樹の個数

グラフの同型性 グラフ G1(V1,E1) と G2(V2,E2) が同型 ⇔ 以下を満たす V1 から V2 への１対1、上への写像 φ が存在 （∀v∊V1)(l(v)=l(φ(v)) （∀(u,v)∊E1)(l(u,v)=l(φ(u),φ(v)) （∀u,v∊V1)((u,v)∊E1 ⇔ (φ(u),φ(v))∊E2) 例 A と B は同型 A と C は同型でない D と E は同型 D と F は同型でない l(v) は頂点の、l(u,v)は辺のラベルを表す (u,v) は無向グラフの時は順番を考えない（ (u,v)=(v,u) ）

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

葉と節点と枝の個数の関係 命題： n 個の葉をもつ有根系統樹は 2n-1 個の節点と 2n-2 個の枝をもち、無根系統樹は 2n-2 個の節点と 2n-3 個の枝をもつ 証明: 有根系統樹についてのみ帰納法により示す。葉が2個の時は明らかに成立。葉が n 個の時、成立すると仮定。 葉を１個追加すると、枝、節点ともに2個増えるので命題が成立。 本講義では内部節点の子は常に２個であることを仮定

系統樹の個数 定理： n 個の葉をもつ同型でない有根系統樹の個数は (2n-3)!! 個、無根系統樹の個数は (2n-5)!! 個である 証明: まず無根系統樹について帰納法で示す。葉が3個の時は成立。 葉が n 個の時、成立すると仮定。 異なる枝に n+1 番目の節点を接続すると、同型でない系統樹が得られる。よって、（追加前の）枝の個数は命題より 2n-3 個なので、 (2n-3)×((2n-5)!!) = (2(n+1)-5)!! より定理が成立。 有根系統樹については n 個の葉をもつ無根系統樹の任意の枝の中点を根とすることに同型でない系統樹が得られるため、定理が成立。 n を奇数とする時、 n!!=n×(n-2)×(n-4)×・・・×1

UPGMA法

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

UPGMA法の例

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

近隣結合法

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

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

近隣結合法（3） 加法性： 節点間の距離 ＝ 節点間を結ぶパスの枝長の和 i と j の親を k とすると、葉 m に対し以下が成立 i k 加法性：　節点間の距離 ＝ 節点間を結ぶパスの枝長の和 i と j の親を k とすると、葉 m に対し以下が成立 i k j m

近隣結合法： アルゴリズム M を葉集合とし、L=M とする |L|>2の間、以下を繰り返す L の中から Dij が最小となるペア (i,j) を選ぶ 新しい節点 k を作り，L 中のすべての m について 　　　　　　　　　　　　　　　　　　　　　　とする k を M に追加し，k と i, j を枝で結び，枝長を 　　　　　　　　　　　　　　　　　　　　　　　　　　　　とする i, j を L から削除し，k を L に追加する 最後に残った i, j 間に枝をはり，その長さを dij とする

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

最節約法

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

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

最節約法： 実行例

最大合致部分系統樹

最大合致部分系統樹 (maximum agreement subtree) 系統樹推定には様々な方法 ⇒ 複数の系統樹を統合 一部の種だけを考えることにより、複数の系統樹から共通の系統樹を得る（⇒種の数の最大化） 入力: 同じラベル集合{1,2,…,n}を持つ有根系統樹 T1,T2,…,TN 出力: Ti|B がすべて同型となる要素数最大の B Ti|B: B に含まれない葉とそれに接続する枝を削除し、さらに子が一つになった内部節点を繰り返し縮約して得る ⇒ B={1,3,5,6,8} 葉の順番は左から右へと並び、保存されると仮定

最小共通祖先 (LCA: Least Common Ancestor) lcai(a,b): a,b をラベルにもつ葉の共通の祖先で最も根から遠いもの 半順序: 節点 u が節点 v の子孫 ⇔ LCAの例 □: lcai(2,3) ○: lcai(4,7) △： lcai(5,7)

動的計画法アルゴリズム a≠b として L(a,b), R(a,b) を次のように定義 すべての a≠b に対して、W(a,b) を動的計画法で計算 ただし、 L(a,b), R(a,b) のいずれかが空の時は、W(a,b)=-∞ すると、 B はトレースバックで 計算可能

動的計画法の例 下図の例に対する計算例（一部分） B={1,3,5,6,8}

時間計算量の解析 定理： 最大合致部分系統樹問題は O(n3N) 時間で計算可能 証明: 正当性の証明は省略。 O(n2) 個の (a,b) と N 個の系統樹について 、LCAを計算するのにかかる時間の合計は O(n2N) 。 L(a,b)（およびR(a,b)）１個あたりの要素数は O(n)であり、あらかじめ lcai(a,b)間の半順序関係の表を作っておけば、全体で O(n3N) 時間。 W(a,b) は全体で O(n3) 時間で計算可能。 子頂点の数が制約されない一般の場合は NP困難

まとめ 補足 系統樹の個数: 無根系統樹で (2n-5)!! 有根系統樹で (2n-3)!! 距離行列法 UPGMA法：　最小距離のクラスタを結合 近隣結合法：　近隣の節点を結合 最節約法: 置換コストが最小の系統樹を計算 最大合致部分系統樹： 複数の系統樹の比較 補足 最尤法に基づく方法も数多く研究 近隣結合法は O(n3) 時間かかるが、この定式化自体における本質的な改善は研究課題と思われる [Simonsen et al.: Proc. WABI 2008] 近年では系統ネットワークについて数多くの研究 系統樹を（ある制約のもとので）複数の親を許すように拡張 合致部分系統樹問題についても数多くの研究 出次数が2の場合（binary tree）に O(Nn2)時間でできるかは研究課題 [Lee et al.:IPL 2005]