樹形間距離

このページでまとめる距離とは、NJ法などで使う配列間距離ではなく樹形間距離である点に注意。また、一部の樹形間距離は樹形探索時のbranch swappingと密接な関係にあるのでそちらも参照のこと。

Unweighted Robinson-Foulds distance

２つの系統樹を比べて、”内分枝をいくつcollapseもしくはexpandすれば両者が一致するか”を距離とする。枝長は考慮しない。OTU数によって取りうる値の上限は変化し、たとえば10 OTUの系統樹同士を比べた場合、0から14の間の整数となる。計算時間はOTU数に比例するが(Day, 1985)、Pattengale et al. (2007)によって高速な近似計算が提案されている。Robinson-Foulds距離はRパッケージ'phangorn'のRF.dist()関数で計算できる。

Unweighted Robinson-Foulds距離は、別の文脈ではpartition metricとも呼ばれる。系統樹から内分枝をひとつ取り除くと２つのsubtreeができるが、このsubtreeにおけるOTU組成を２つの系統樹で比べ、一致しなかった数を樹形間距離として表す(partition metric)。たとえば、右の図(Penny and Hendy, 1985から引用)の系統樹aから、内分枝(a)を取り除くと、 (cow, pig, sheep, horse)のsubtreeと、 (human, ape, monkey, mouse, rabbit, dog, kanga)のsubtreeができる。系統樹b,c,d,eは系統樹aとは異なる樹形だが、いずれの樹形でも、(a)で示した位置にある内分枝を取り除くと、上記のOTU組成のsubtreeが生成される。このように、ある内分枝を取り除いたときにできる２つのsubtreeのOTU組成をpartition、あるいはbipartitionと呼ぶ。このとき、subtreeのOTU組成のみがpartitionの同一性を判断する指標となり、subtreeの樹形は考慮されないことに注意。これに対して、系統樹aの内分枝(b)を取り除いてできるsubtreeのOTU組成は、系統樹b,c,d,eのどの内分枝を取り除いたときにも見られない。このように、系統樹間で異なるpartitionを生み出す枝を数えることで、樹形間距離を算出する。

Robinson, D.F. and Foulds, L.R. (1981). Comparison of phylogenetic trees. Math. Biosci. 53: 131–147.

Day, W.H.E. (1985). Optimal algorithms for comparing trees with labeled leaves. J. Classif. 2: 7–28.

Pattengale, N.D., Gottlieb, E.J., and Moret, B.M.E. (2007). Efficiently computing the Robinson-Foulds metric. J. Comput. Biol. 14: 724–35.

Penny, D. and Hendy, M.D. (1985). The Use of Tree Comparison Metrics. Syst. Zool. 34: 75–82.

Weighted Robinson-Foulds distance

Unweighted Robinson-Foulds距離を計算する際に、枝長で重み付けを行う。より長い枝の変更が必要な場合、算出される距離は大きくなる。

Robinson, D.F. and Foulds L. R. (1979). Comparison of weighted labelled trees. Comb. Math. VI 748: 119–126.

Nearest-neighbor interchange distance (NNI distance)

"ある樹形からある別の樹形へ移行するとき、最少で何回のNNI操作が必要か"を指標にした距離。Waterman and Smith (1978)が発案した。１回のNNI操作は、Robinson-Foulds距離でいう１回分のcollapse＋１回分のexpandに相当するが、NNI距離はUnweighted Robinson-Foulds距離の1/2とならないこともある（詳しい説明はこのページ（外部リンク）を参照）。NNI距離は、R package 'ape'のdist.topo()関数で計算できる(method="PH85"を指定)。

Matsen (2006)から引用

Matsen, F. (2006). A Geometric Approach to Tree Shape Statistics. Syst. Biol. 55: 652–661.

Waterman, M.S. and Smith, T.F. (1978). On the similarity of dendrograms. J. Theor. Biol. 73: 789–800.

Subtree pruning and regrafting distance (SPR distance)

"ある樹形からある別の樹形へ移行するとき、最少で何回のSPR操作が必要か"を指標にした距離。DasGupta et al., (1997)では、subtree-transfer distanceと呼ばれている。RSPR software packageを使えば、数百OTUの系統樹であっても、SPR距離を１秒以下で計算可能。

変法にLinear-cost subtree-transfer distanceがある (DasGupta et al., 1997)。この方法では、より遠い位置への枝の挿入にコストを課す。Subtreeの切断点と挿入点の間の枝長で加重しつつ樹形間距離を計算する。枝長を持たない（＝すべての枝が同じ長さをもつ）系統樹の場合、Linear-cost subtree-transfer distanceはNNI distanceと一致する (DasGupta et al., 1997)。

DasGupta, B., He, X., Jiang, T., Li, M., and Tromp, J. (1999). On the Linear-Cost Subtree-Transfer Distance between Phylogenetic Trees. Algorithmica 25: 176–195.

Tree bisection and reconnection distance (TBR distance)

"ある樹形からある別の樹形へ移行するとき、最少で何回のTBR操作が必要か"を指標にした距離。

Quartet metric

無根系統樹から４つのOTUを抜き出すと、その樹形は((A,B),(C,D))、((A,C),(B,D))、((A,D),(B,C))の３通りのうちのどれかになる。この４OTUからなる小さな系統樹をquartetと呼ぶ（下図：Zhaxybayeva et al. (2006)から引用）。２つの樹形の間で、すべての４OTU組み合わせのquartetを比べ、樹形が異なるquartetの数を樹形間距離quartet metricとする。枝長の違いは考慮されない。Estabrook et al. (1985)が提唱した。ペアワイズの距離だけでなく、３つ以上の樹形の比較にも使える。

Quartetの概念についてはこのページ（外部リンク）で平易に説明してある。

Estabrook, G.F., McMorris, F.R., and Meacham, C.A. (1985). Comparison of Undirected Phylogenetic Trees Based on Subtrees of Four Evolutionary Units. Syst. Biol. 34: 193–200.

Zhaxybayeva, O., Gogarten, J.P., Charlebois, R.L., Doolittle, W.F., and Papke, R.T. (2006). Phylogenetic analyses of cyanobacterial genomes: quantification of horizontal gene transfer events. Genome Res. 16: 1099–108.

Triples metric

Quartet metricは無根系統樹に対して用いられるが、その有根系統樹版。系統樹からOTUを３つ抜き出して３OTUと根からなる小さな系統樹を作り、樹形が異なるtriplesの数を樹形間距離triples metricとして扱う。Dobson (1975)が発案した。枝長の違いは考慮されない。ペアワイズの距離だけでなく、３つ以上の樹形の比較にも使える。

Dobson, A.J. (1975). Comparing the shapes of trees. Comb. Math. III 452: 95–100.

Nodal distance

すべての組み合わせの２OTU間の枝長を２つの樹形の間でくらべ、その差の総和を樹形間距離とする方法。Bluis and Shin (2003)では枝長は考慮されていないが、枝長ありの系統樹でも実行できるはず。無根系統樹に対して使用される。

Bluis and Shin (2003)から引用

Bluis, J. and Shin, D.G. (2003). Nodal distance algorithm: calculating a phylogenetic tree comparison metric. In Third IEEE Symposium on Bioinformatics and Bioengineering, 2003. Proceedings. (IEEE Comput. Soc), pp. 87–94.

Split nodal distance

Nodal distanceの有根系統樹版。２OTU間の枝長を、片方のOTUからmost recent common ancestor (MRCA)までの枝長と、そこからもう片方のOTUまでの枝長に分けて評価する。PhyloNetwork.pyに実装してある。

Cardona, G., Llabrés, M., Rosselló, F., and Valiente, G. (2010). Nodal distances for rooted phylogenetic trees. J. Math. Biol. 61: 253–76.

Branch score

２つの系統樹の同一の枝の長さを比べる方法。枝長の差の平方和を全て足し合わせた数を樹形間距離とする。樹形が異なる場合、ある枝は片方の系統樹には存在するがもう片方にはない、という状況が生まれるが、その際は長さ０の枝との比較として処理する。よって、短い枝について樹形が異なっていても、長い枝の違いほどは距離の大きさに現れない。R package 'ape'のdist.topo()関数で計算できる(method="score"を指定)。

Kuhner, M. and Felsenstein, J. (1994). A simulation comparison of phylogeny algorithms under equal and unequal evolutionary rates [published erratum appears in Mol Biol Evol 1995 May;12(3):525]. Mol. Biol. Evol. 11: 459–468.

Transposition distance

Valiente (2005)が発案。Alberich et al. (2009)によると、"The fact that our transposition distance is induced by a metric in a symmetric group allows the use of the algebraic machinery of group theory to study it."らしい。計算時間はOTU数に比例する。PhyloNetwork.pyに実装してある。

Valiente, G. (2005). A Fast Algorithmic Technique for Comparing Large Phylogenetic Trees. Lect. Notes Comput. Sci. 3772: 370–375.

Alberich, R., Cardona, G., Rosselló, F., and Valiente, G. (2009). An algebraic metric for phylogenetic trees. Appl. Math. Lett. 22: 1320–1324.

TreeKO

異なる遺伝子の系統樹同士を比べると、遺伝子の重複等によってOTU数が一致しないことがあるが、そのような状況でも系統樹間の距離を算出してくれる。

Marcet-Houben and Gabaldón (2011)から引用

Marcet-Houben, M. and Gabaldón, T. (2011). TreeKO: a duplication-aware algorithm for the comparison of phylogenetic trees. Nucleic Acids Res. 39: e66.

Average standard deviation of split frequency (ASDSF)

樹形間の距離を比べる上記の方法とは異なり、ASDSFは樹形の分布同士を比べる方法である。系統樹の分布（複数の系統樹の集まり）からbipartitionの出現頻度を取得し、それが分布間でどれくらい異なっているかを標準偏差として算出する。MrBayesの樹形探索において、複数のMCMCMC鎖の収束判定に用いられる。このページ（外部リンク）に詳しく説明されている。

その他の方法

Lapointe, F.-J. and Legendre, P. (1990). A Statistical Framework to Test the Consensus of Two Nested Classifications. Syst. Zool. 39: 1.

Page updated

Google Sites

Report abuse