樹形空間の可視化

複数の系統樹の類似度を、たとえば二次元の散布図として表す場合、（1）樹形間の距離行列の作成と、(2)距離行列を元にした二次元座標の計算、が必要になり、どちらのステップにも複数の方法がある。このページでは(2)についてまとめる。

Amenta and Klingner (2002)の方法

樹形空間を描き出す際に元となる距離行列は多次元のデータであるため、可視化の際は次元を縮小しなければならない。Amenta and Klingner (2002)は次元縮小に多次元尺度構成法 Multidimensional scaling (MDS)を採用している。MDSでは応力関数(stress function)を最小化することで多次元空間上での位置関係をできるだけ歪ませずに、つまり、データ点同士の距離をできるだけ保存したまま低次元上（１−３次元）に投影する。散布図として出力されるが、x軸やy軸は特に意味を持たない。Mesquiteに組み込まれている"Tree Set Visualization module"では、Kruskal-1関数が応力関数として使用されているようだ。樹形間の距離行列はRobinson-Foulds距離を採用している。

Amenta and Klingner (2002)から引用

Amenta, N. and Klingner, J. (2002). Case study: visualizing sets of evolutionary trees. In IEEE Symposium on Information Visualization, 2002. INFOVIS 2002. (IEEE Comput. Soc), pp. 71–74.

Hillis, D.M., Heath, T.A., and St John, K. (2005). Analysis and visualization of tree space. Syst. Biol. 54: 471–82.

Höhna and Drummond (2012)の方法

樹形間の距離はNNI distanceを採用し、次元縮小にはMDSを使用している。下の図では、NNI distance = 1で結ばれる樹形同士を線で結んでいる。

Höhna and Drummond (2012)から引用

Höhna, S. and Drummond, A.J. (2012). Guided tree topology proposals for Bayesian phylogenetic inference. Syst. Biol. 61: 1–11.

Whidden and Matsen (2015)の方法

Hillis et al. (2005)の方法は、Robinson-Foulds距離を使っているが、tree swappingによる樹形の探索過程を可視化する場合、この方法は必ずしも最適ではない。（非加重の）Robinson-Foulds距離は、"２つの樹形の間の距離はNNI何回分か"に比例するのに対し、近年の樹形探索アルゴリズムは、NNIよりも探索範囲の広いSPRやTBRをbranch swappingに採用している。そこで、SPR distanceをもとにグラフを描くのがWhidden and Matsen (2015)の方法である。論文中ではMDSによる次元縮小も取り扱っているが、主題はgraph-based approachである。樹形間の距離行列からグラフを作成し、Cytoscapeで可視化している。枝長は考慮していない。

以下の３通りのグラフを紹介している。2.では、SPR距離の半径をもとにした反復的なクラスタリング法を実装している。

1. Distance SPR graph: 尤度が最も高い系統樹からの距離に応じて色分け

2. Cluster SPR graph: 樹形をクラスタリングし、所属するクラスターごとに色分け

3. Weighted MCMC graph: MCMCで樹形を探索したときに、100世代以内の間隔で現れた樹形同士を線で結ぶ

Whidden and Matsen (2015)から引用

Whidden, C. and Matsen, F.A. (2015). Quantifying MCMC exploration of phylogenetic tree space. Syst. Biol. 64: 472–91.