生命情報学基礎論 - Kyoto University Bioinformatics

生命情報学基礎論（３）
進化系統樹推定
阿久津達也
京都大学化学研究所
バイオインフォマティクスセンター
講義予定













４月１３日（月）: 生命情報学の基盤
４月２０日（月）：配列の比較と相同性検索
４月２７日（月）：進化系統樹推定
５月１日（金）：隠れマルコフモデル
５月１１日（月）：遺伝子ネットワークの解析と制御（田村）
５月１８日（月）：タンパク質立体構造予測
５月２５日（月）、６月１日（月）：カーネル法
６月８日（月）：代謝ネットワークの堅牢性（田村）
６月１５日（月）：生物情報ネットワークの構造解析
６月２２日（月）：木の編集距離（田村）
６月２９日（月）：タンパク質相互作用予測（林田）
７月６日（月）：タンパク質複合体予測（林田）
７月１３日（月）：生物データの圧縮による比較（林田）
進化系統樹
進化系統樹



種間（もしくは遺伝子間）の進化の関係を表す木
以前は形態的特徴をもとに構成
現在は配列情報をもとに構成
有根系統樹と無根系統樹



有根系統樹: 根（共通の祖先に対応）がある系統樹
無根系統樹: 根のない系統樹
いずれも葉にのみラベル（種に対応）がつく
有根系統樹
無根系統樹
系統樹を扱う際は、頂点でなく節点という用語を使う
進化系統樹の個数
系統樹の同型性



同型な系統樹：本質
的に同じつながり方
（グラフとして同型）
をした系統樹
(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

距離の性質
Dkl 
Dil | Ci |  D jl | C j |
| 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 の子節点）
S k (a)  min ( Si (b)  S (a, b))  min ( S j (b)  S (a, b))
b
k が葉の場合
 0 if a  sk [1]
S k ( a)  
  otherwise
b
最節約
法：
実行例
S k (a)  min ( Si (b)  S (a, b))  min ( S j (b)  S (a, b))
b
b
最尤法
最尤法による系統樹推定


最尤法：統計学の一般的手法
系統樹の尤度（確率）
P(s1 ,, sn | T , t ) 
 P( s
2 n 1
sn1 ,, s2 n1


)  P(si | s p (i ) , ti )
i 1
P(B|A,t): 塩基Aがt時間後に塩
基Bになる確率
配列 s1,…,sn に対し、尤度最大
の系統樹のトポロジー T と、
枝長 ti を計算


2 n2
ただし、p(i) は i の親節点
この計算は難しく、様々な手法
が提案されている
尤度計算の例

1塩基あたりの尤度
P( xu1 , xu2 | T , t1 , t2 )   qa P( xu1 | a, t1 ) P( xu2 | a, t2 )
a

配列全体の尤度
N
P( x1 , x 2 | T , t1 , t2 )   P( xu1 , xu2 | T , t1 , t2 )
u 1
ブートストラップ法

系統樹の信頼性




推定された系統樹の信頼性は不明
⇒信頼性評価の必要性
必ずしも系統樹全体でなくても、大きな分岐などの特定の特
徴の信頼性を評価できれば良い
⇒ブートストラップ法による評価
ある確率モデルのもとで、
ブートストラップ法による頻度≈ 特徴の事後確率
系統樹に対するブートストラップ法
1.
2.
3.
もとのアラインメントから各カラムを重複を許してランダムに抽出
ステップ 1 で作ったアラインメントから系統樹を推定
ステップ 1,2 を数多く（例えば1000回）繰り返し、各特徴の頻度分布を計
算し、頻度により信頼性を評価
まとめ

系統樹の個数


距離行列法




無根系統樹で (2n-5)!! 有根系統樹で (2n-3)!!
UPGMA法：最小距離のクラスタを結合
近隣結合法：近隣の節点を結合
最節約法: 置換コストが最小の系統樹を計算
進化の確率モデル:



Jukes-Cantor行列を用いて配列間の置換確率を計算
最尤法：確率が最大となる系統樹を推定
ブートストラップ法：系統樹の特徴の信頼性評価

Download Report