車輪樹法

車輪樹法は進化系統情報を直感的
かつ情報豊かに,さらに最も偏り
なく表現するための手法です.

Menu

トップ
車輪樹を作る
車輪樹のポイント
車輪樹の例
ウェブAPI
ダウンロード
NHXフォーマット
車輪樹の理論
文献
Extra

Languages

/

Contact

岩崎 渉
東京大学
大学院理学系研究科
生物科学専攻
メール:
iwasaki AT bs.s.u-tokyo.ac.jp

License

車輪樹法ソフトウェア:
GNU General Public License
その他のコンテンツ:
Creative Commons License

車輪樹のアルゴリズムと巡回セールスマン問題

下図は車輪樹を生成するアルゴリズムをまとめたものです.

まず系統樹群から与えられた閾値をもとにコンセンサス系統樹を作成します(各系統樹には観測回数等に比例した重みを与えることが可能).

次に,コンセンサス系統樹の各多分枝ノード(v)について,その周りの枝(v-branches)の最もよい並び順を以下により決定します.

(1) v-branchesの各枝ペアに関して,系統樹群全てについて距離の和を計算する.
(2) これを,各枝を都市と見なしたときの都市間距離とする.
(3) 全都市を巡回する時の総移動距離を最小にする巡回セールスマン問題を解き,これをv-branchesの車輪の回りの並び順とする(これはアイデアで触れた,系統樹群の中で近くにある枝をなるべく隣りあうように置くことに相当します).

これを全ての多分枝ノードについて繰り返すことで,車輪樹が得られます.

最も偏りのないセントロイド表現としての車輪樹

車輪樹はすでに述べたアイデアを実装しただけでなく,数学的にセントロイドにあること,すなわち,系統樹群の最も偏りのない表現であることが示されます.
直感的な説明を以下に与えます.

表面に系統樹の絵が描かれているたくさんの石があり,それぞれの石の重さはその系統樹が真である確率に比例しているとします(最善樹はもっとも重い石に対応する).
これらの石を,似た系統樹が描かれている石同士が近くに来るように置くと,いわば系統樹群に関する「地図」が作成されます.
このとき,一般に超高次元空間における推定問題においては,最も重い石が地図の中心にくるとは限りません.
車輪樹法は,最も重い石の代わりに,この地図上で最もバランスが取れている点,すなわち重心にあたる点を見つけるための手法です.

より詳しくは文献を参照してください.