情報生命科学特別講義

情報生命科学特別講義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）
有根系統樹： 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)!!
葉と節点と枝の個数の関係
命題： 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)

距離行列法の一つ


距離行列法：葉のペアの距離データから系統樹を構成
アルゴリズム


各配列のみからなるクラスタを作成
クラスタが２個になるまで以下を繰り返す



クラスタ間距離が最小のクラスタどうしを併合
新しくできたクラスタと他のクラスタ間の距離を計算
クラスタ間距離
1
Dkl 
dij

| Ck || Cl | iCk , jCl

距離の性質
Dil | Ci | Djl | C j |
Dkl 
| Ci |  | C j |
UPGMA法の例
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法の正当性
分子時計＝進化速度一定性の仮定
 枝長＝分子時計により刻まれた時間
 分子時計仮説が成立 
「任意の葉までの枝長の和が等しい」が任意節点について成立
⇒UPGMA法は系統樹を正しく再構成
以下の例で、(a) は仮説を満たさないが、(b)は満たす

近隣結合法
近隣結合法（１）
UPGMA法では以下の例(a)で、2と3が最初に選ばれたため、
正しい系統樹を再構成できなかった
 最初に、3と4、もしくは、1と2が選ばれれば良い
 つまり、兄弟関係（近隣関係）にある葉が選ばれれば良い
 近隣結合法では（距離が加法性を満たすという仮定のもとで）
常に近隣関係にある葉を選ぶ

近隣結合法（2）

近隣結合法



距離が加法性を満たせば系統樹を正しく再構成
ただし、計算されるのは無根系統樹
加法性：節点間の距離＝節点間を結ぶパスの枝長の和
近隣結合法（3）


加法性：節点間の距離＝節点間を結ぶパスの枝長の和
i と j の親を k とすると、葉 m に対し以下が成立
dkm  12 (dim  d jm  dij )
i
k
m
j
近隣結合法：アルゴリズム

M を葉集合とし、L=M とする
|L|>2の間、以下を繰り返す

L の中から Dij が最小となるペア (i,j) を選ぶ
 新しい節点 k を作り，L 中のすべての m について
dkm  12 (dim  d jm  dij ) とする
 k を M に追加し，k と i, j を枝で結び，枝長を
dik  12 (dij  ri  rj ), d jk  dij  dik とする
 i, j を L から削除し，k を L に追加する
最後に残った i, j 間に枝をはり，その長さを dij とする


ただし、 Dij  dij  (ri  rj ), ri  |L1|2 dik
kL
アウトグループ


近隣結合法：無根系統樹しか計算されない
無根系統樹における根の決定法


最も長い葉の間の中点を根とする
対象とする種と離れていることが明らかな種（アウトグループ）を追加して
系統樹を作成し、アウトグループに接続する接点を根とする
最節約法
最節約法：問題設定


最小コストの置換で各配列を生成する系統樹を計算
２種類の探索が必要


系統樹の形状（トポロジー)
⇒ 難しい
内部節点への配列の割り当て ⇒ 動的計画法で計算可能
最節約法：アルゴリズム




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
最大合致部分系統樹
最大合致部分系統樹 (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 の子孫 ⇔ u  v (u  v)
LCAの例
□: lcai(2,3)
○: lcai(4,7)
△： lcai(5,7)
動的計画法アルゴリズム
a≠b として L(a,b), R(a,b) を次のように定義
L(a, b)  { (a, x) | Ti (lcai (a, x)  lca i (a, b)) }
R(a, b)  { ( x, b) | Ti (lcai ( x, b)  lca i (a, b)) }
すべての a≠b に対して、W(a,b) を動的計画法で計算
W (a, a)  1
W (a, b)  max {W (a, c)}  max {W (c, b)}
( a ,c )L ( a ,b )
( c,b )R ( a,b )
ただし、 L(a,b), R(a,b) のいずれかが空の時は、W(a,b)=-∞
すると、 | B | max{W (a, b)}
ab
B はトレースバックで
計算可能
動的計画法の例
下図の例に対する計算例（一部分）
L(1,3)  {(1,1)}
R(1,3)  {(3,3)}
L(5,8)  {(5,5), (5,6)} R(5,8)  {(8,8)}
W (1,3)  W (1,1)  W (3,3)  2
W (5,8)  W (5,6)  W (8,8)  3
W (1,8)  W (1,3)  W (5,8)  5
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]

Download Report