TreefinderとPhylogearsを用いたParallel
Likelihood Ratchetによる最尤系統推定

尤度ってナニ?

●あるモデルが正しい状況で、手元のデータが実現する確率進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

尤度ってナニ?

●あるモデルが正しい状況で、手元のデータが実現する確率●

10回のコイントスで表1回裏9回になった

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

尤度ってナニ?

●あるモデルが正しい状況で、手元のデータが実現する確率●

10回のコイントスで表1回裏9回になった–「コイントスでは表裏の出る比率は1:9」というモデルの尤度は(1/10)×(9/10)9=0.03874205

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

尤度ってナニ?

●あるモデルが正しい状況で、手元のデータが実現する確率●

10回のコイントスで表1回裏9回になった–「コイントスでは表裏の出る比率は1:9」というモデルの尤度は(1/10)×(9/10)9=0.03874205–「コイントスでは表裏は同じ比率で出る」というモデルの尤度は(1/2)10=0.0009765625

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

尤度ってナニ?

●あるモデルが正しい状況で、手元のデータが実現する確率●●

10回のコイントスで表1回裏9回になった–「コイントスでは表裏の出る比率は1:9」というモデルの尤度は(1/10)×(9/10)9=0.03874205–「コイントスでは表裏は同じ比率で出る」というモデルの尤度は(1/2)10=0.0009765625

モデルのデータへの当てはまりの良さを表す

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

尤度ってナニ?

●あるモデルが正しい状況で、手元のデータが実現する確率●

10回のコイントスで表1回裏9回になった–「コイントスでは表裏の出る比率は1:9」というモデルの尤度は(1/10)×(9/10)9=0.03874205–「コイントスでは表裏は同じ比率で出る」というモデルの尤度は(1/2)10=0.0009765625●

モデルのデータへの当てはまりの良さを表す●

コンピュータに扱いやすい対数尤度を用いる
進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

最尤系統推定におけるパラメータ●

分子進化モデル●系統モデル●枝長 (と枝長比)

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

最尤系統推定におけるパラメータ●●

分子進化モデルA

系統モデル●枝長 (と枝長比)

●

樹形
–

3OTU：1通り–

4OTU：3通り–

5OTU：3×5通り–

6OTU：3×5×7通り

–

B

C

A

C

A

B

B

D

C

D

176

100OTU：1700459×10

B

ACD

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

最尤系統推定におけるパラメータ●●

分子進化モデルA

系統モデル●枝長 (と枝長比)●

樹形–

3OTU：1通り–

4OTU：3通り–

5OTU：3×5通り–

6OTU：3×5×7通り

–

B

C

A

C

A

B

B

D

C

D

176

100OTU：1700459×10

B

A

C

D

尤度が最大になるこれらを決定する＝最尤系統推定
進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

最尤系統推定における初期値

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

最尤系統推定における初期値●

尤度最大化を始めるには良い初期値が必要進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

最尤系統推定における初期値●●

尤度最大化を始めるには良い初期値が必要
分子進化モデルの初期値は初期樹形が決まれば最節約的に決定可能

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

最尤系統推定における初期値●●●

尤度最大化を始めるには良い初期値が必要
分子進化モデルの初期値は初期樹形が決まれば最節約的に決定可能初期樹形をどのように与えるか?

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

最尤系統推定における初期値●●●

尤度最大化を始めるには良い初期値が必要
分子進化モデルの初期値は初期樹形が決まれば最節約的に決定可能初期樹形をどのように与えるか?
●

近隣結合法

●

段階的配列付加法

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

最尤系統推定における局所探索
樹形空間

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

最尤系統推定における局所探索
樹形空間

初期樹形

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

最尤系統推定における局所探索
樹形空間

初期樹形
樹形改変によって探索される範囲
進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

最尤系統推定における局所探索
樹形空間

仮の最尤系統樹
初期樹形
樹形改変によって探索される範囲
進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

最尤系統推定における局所探索
樹形空間

仮の最尤系統樹

初期樹形
樹形改変によって探索される範囲
進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

最尤系統推定における局所探索
樹形空間

仮の最尤系統樹

初期樹形
樹形改変によって探索される範囲
進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

最尤系統推定における局所探索
樹形空間

初期樹形
樹形改変によって探索される範囲
進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

最尤系統推定における局所探索
樹形空間

より尤度の高い系統樹が見つからなかったら、その時点で最も尤度が高いものを最尤系統樹として採用

初期樹形
樹形改変によって探索される範囲
進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

最尤系統推定における局所探索
樹形空間

より尤度の高い系統樹が見つからなかったら、その時点で最も尤度が高いものを最尤系統樹として採用

真の最尤系統樹

初期樹形
樹形改変によって探索される範囲
進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

最尤系統推定における局所探索
樹形空間

より尤度の高い系統樹が見つからなかったら、その時点で最も尤度が高いものを最尤系統樹として採用

真の最尤系統樹
初期系統樹が十分に真の最尤系統樹に近くなくてはならない

初期樹形
樹形改変によって探索される範囲
進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

ショットガン的局所探索
樹形空間
初期樹形

真の最尤系統樹
初期樹形

初期樹形
樹形改変によって探索される範囲

初期樹形

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

ショットガン的局所探索
樹形空間
初期樹形

真の最尤系統樹
初期樹形
何らかの方法でばらつかせた初期樹形からの局所探索を繰り返す初期樹形
樹形改変によって探索される範囲

初期樹形

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

ショットガン的局所探索
樹形空間
初期樹形

真の最尤系統樹
初期樹形
何らかの方法でばらつかせた初期樹形からの局所探索を繰り返す

Likelihood Ratchet
初期樹形
樹形改変によって探索される範囲

初期樹形

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

Likelihood Ratchet

OTU1
OTU2
OTU3

...

...

...

OTUN

TGTTT ... TTTTCAGTAC ... TTTTCAGTAT ... TTGTCAGTAT ... ATTTC

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

Likelihood RatchetOTU1OTU2OTU3TGTTT ... TTTTCAGTAC ... TTTTCAGTAT ... TTGTC
...

...

...

OTUN
AGTAT ... ATTTC
weight 11111 ... 11111
無作為に重複を許してサイト数の20～25%加重進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

Likelihood Ratchet

OTU1
OTU2
OTU3

TGTTT ... TTTTCAGTAC ... TTTTCAGTAT ... TTGTC
...

...

...

OTUN
AGTAT ... ATTTC
weight 12113 ... 12112
無作為に重複を許してサイト数の20～25%加重進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

Likelihood Ratchet

1.無作為に重複を許してサイト数の20～25%を加重進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

Likelihood Ratchet

1.無作為に重複を許してサイト数の20～25%を加重
2.加重データで系統推定or初期樹形生成

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

Likelihood Ratchet

1.無作為に重複を許してサイト数の20～25%を加重
2.加重データで系統推定or初期樹形生成
3.その結果を初期樹形として元データで系統推定

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

Likelihood Ratchet

元データの尤度
尤度

樹形空間

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

Likelihood Ratchet●

加重

元データの尤度
尤度

無作為加重により尤度のLandscapeが変化する

加重加重データの尤度

樹形空間

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

Likelihood Ratchet●

加重

元データの尤度
尤度●

無作為加重により尤度のLandscapeが変化する
Landscapeの変化によって、尤度の谷が無くなったり越えやすくなることがある

加重加重データの尤度

樹形空間

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

Likelihood Ratchet●

加重

元データの尤度
尤度

●

●

加重
加重データの尤度

無作為加重により尤度のLandscapeが変化する
Landscapeの変化によって、尤度の谷が無くなったり越えやすくなることがある谷を越えた(かもしれない)結果を初期樹形として与えて元データの系統推定を行うことを繰り返す

樹形空間

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

Likelihood Ratchet●

加重

元データの尤度
尤度

●

●

加重
加重データの尤度●

無作為加重により尤度のLandscapeが変化する
Landscapeの変化によって、尤度の谷が無くなったり越えやすくなることがある谷を越えた(かもしれない)結果を初期樹形として与えて元データの系統推定を行うことを繰り返す
これにより、より多くの尤度の山を把握する

樹形空間

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

Likelihood Ratchet●

加重

元データの尤度
尤度

●

●

加重
加重データの尤度●

無作為加重により尤度のLandscapeが変化する
Landscapeの変化によって、尤度の谷が無くなったり越えやすくなることがある谷を越えた(かもしれない)結果を初期樹形として与えて元データの系統推定を行うことを繰り返す
これにより、より多くの尤度の山を把握する

これまでのPAUP*4+PAUPRatは並列処理や比例・分離モデルに非対応
樹形空間

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

Likelihood Ratchet●

加重

元データの尤度
尤度

●

●

加重
加重データの尤度●

無作為加重により尤度のLandscapeが変化する
Landscapeの変化によって、尤度の谷が無くなったり越えやすくなることがある谷を越えた(かもしれない)結果を初期樹形として与えて元データの系統推定を行うことを繰り返す
これにより、より多くの尤度の山を把握する

これまでのPAUP*4+PAUPRatは並列処理や比例・分離モデルに非対応
樹形空間

Treefinder+Phylogears
進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

Phylogearsの概要

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

Phylogearsの概要●

Likelihood Ratchetの並列処理●

無作為加重データでの初期樹形生成を並列処理●

多数の初期樹形からの最尤系統樹探索を並列処理

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

Phylogearsの概要●●

Likelihood Ratchetの並列処理●

無作為加重データでの初期樹形生成を並列処理●

多数の初期樹形からの最尤系統樹探索を並列処理

ブートストラップ解析を並列処理●

多数のリサンプリングデータにおける最尤系統樹探索を並列処理

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

Phylogearsの概要●●

Likelihood Ratchetの並列処理●

無作為加重データでの初期樹形生成を並列処理●

多数の初期樹形からの最尤系統樹探索を並列処理

ブートストラップ解析を並列処理●●

多数のリサンプリングデータにおける最尤系統樹探索を並列処理

その他色々

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

Phylogearsが中でやっていること

データファイルの入力

無作為加重Phylogears
PAU P*
Treefi nder

初期系統樹からの系統推定

最尤系統樹

初期系統樹群

加重データ
系統推定または無作為配列付加による初期系統樹生成

PAU P*/PH YLIPT N T /Treefi nder

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

一括処理ファイルのコピペ

Kakusan3の出力したTreefinderフォルダへコピー
進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

一括処理ファイルの編集

テキストエディタで開いて編集

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

一括処理ファイルの編集

最大反復数を指定

最大並列処理数を指定

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

一括処理ファイルの実行進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

実行画面

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

完了後に出力されるファイル群

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

一括処理ファイルの編集 ブートストラップ解析

テキストエディタで開いて編集

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

一括処理ファイルの編集 ブートストラップ解析

最大反復数を指定

最大並列処理数を指定

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

完了後に出力されるファイル群 ブートストラップ解析

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

まとめ

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

まとめ●

OTUの多いデータでは樹形空間は広大になってしまう

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

まとめ
●

●

OTUの多いデータでは樹形空間は広大になってしまう
そんなデータでも効率的に樹形空間内を探索する方法がLikelihood Ratchet

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

まとめ
●

●

●

OTUの多いデータでは樹形空間は広大になってしまう
そんなデータでも効率的に樹形空間内を探索する方法がLikelihood Ratchet
Likelihood Ratchetは、尤度のLandscapeを人為的に改変することで尤度の谷を越えやすくする

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

まとめ
●

●

●

●

OTUの多いデータでは樹形空間は広大になってしまう
そんなデータでも効率的に樹形空間内を探索する方法がLikelihood Ratchet
Likelihood Ratchetは、尤度のLandscapeを人為的に改変することで尤度の谷を越えやすくする
TreefinderとPhylogearsを組み合わせることで、この樹形探索を並列処理することが可能

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用

まとめ
●

●

●

●

●

OTUの多いデータでは樹形空間は広大になってしまう
そんなデータでも効率的に樹形空間内を探索する方法がLikelihood Ratchet
Likelihood Ratchetは、尤度のLandscapeを人為的に改変することで尤度の谷を越えやすくする
TreefinderとPhylogearsを組み合わせることで、この樹形探索を並列処理することが可能
ブートストラップ解析も同様に並列処理が可能

進化モデル選択とLikelihood Ratchet、系統樹から進化速度の変化を検出する
田辺 晶史 (東北大・院・生命科学)
2009年生態学会自由集会：進化生態学のための分子系統樹の推定と応用