系統樹の個数

2019/5/29 2限の分子進化学の講義中に先生がさらっと「系統樹の個数は奇数だけをかければ良いので」と言っていて、:thinking_face:となったので、それについて考える。

対象とする種の数（葉の個数）を $n$ としたとき、「本質的に形状が異なる木の個数」とは、「（葉のラベルを考慮したうえで）同型(isomorphic)ではない木の個数」のことである。「同型」の数学的な定義は最後に書いた。

定理）$n$ 個（$n\geq 3$）の葉を持つ同型でない系統樹の個数

有限系統樹： $(2n-3)!!$

無根系統樹： $(2n-5)!!$

※ $n$ を奇数とするとき、$n!!$ を次のように定義している。

$$n!! = n\times(n-2)\times(n-4)\times\cdots\times1$$

節点・枝・葉の関係

葉の個数に関する帰納法（といえば大げさだが、葉を $1$ つ取り除くと枝の数、節点の数が共に $2$ 個減少することは明らか）を用いれば、以下の性質が簡単に説明できる。

用語	説明	有根系統樹	無根系統樹
葉	次数が $1$ の節点で、現存する、もしくは、対象とする $1$ つの生物種に対応する。葉はラベルを持ち、異なる葉には異なるラベルが割り当てられる。	$n$	$n$
節点	木の葉もしくは枝分かれ部分をいう。	$2n-1$	$2n-2$
枝（辺）	節点の対で、種の親子関係を表す。	$2n-2$	$2n-3$

系統樹の個数

無根系統樹

こちらも葉の個数に関する帰納法によって証明できる。葉が $3$ 個の時に、無根系統樹に対して定理が成立することは明らか。

ここで、葉が $n$ 個の時に定理が成立するものと仮定する。この時 $n+1$ 個目のラベルは $2n-3$ 個の枝のどこにでも挿入することができ、この時異なる枝を選ぶと異なる系統樹が構成できる。

したがって、$n+1$ 個の葉をもつ無根系統樹の個数は、

$$(2n-3)\times((2n-5)!!) = (2(n+1)-5)!!$$

となり、証明が完了する。

有根系統樹

無根系統樹の任意の枝の中間に根を配置することにより、有根系統樹が構成できることを利用する。

$n$ 個の葉を持つ無根系統樹の $2n-3$ 個の異なる枝に根を追加することで得られる有根系統樹は異なるので、

$$(2n-3)\times((2n-5)!!)=(2n-3)!!$$

となり、有根系統樹に関しても定理が成立する。

グラフの同型性

定義

$G_1(V_1,E_1),G_2(V_2,E_2)$ をそれぞれグラフ

$\Sigma_V$ と $\Sigma_E$ を集合

各頂点 $v$ には $\Sigma_V$ の要素がラベル $l(v)$ として割り当てられている

各辺 $e$ には $\Sigma_E$ の要素がラベル $l(e)$ として割り当てられている

$e=(u,v)$ のとき、$l(e)=l(u,v)$ と書く

ここで、$V_1$ から $V_2$ への全単射の写像 $\phi$ が存在し、かつ以下の条件を満たすとき、$G_1$ および $G_2$ は同型であるという。

$(\forall v\in V_1)(l(v) = l(\phi(v)))$
$(\forall(u,v)\in E_1)(l(u,v) = l(\phi(u),\phi(v)))$
$(\forall u\in V_1,\forall v\in V_1)((u,v)\in E_1\Longleftrightarrow(\phi(u),\phi(v))\in E_2)$

系統樹の個数

系統樹の個数

節点・枝・葉の関係

系統樹の個数

無根系統樹

有根系統樹

グラフの同型性

Table of Contents

Published

Last Updated

Category

Tags

Contact

Other contents

系統樹の個数

節点・枝・葉の関係

系統樹の個数

無根系統樹

有根系統樹

グラフの同型性

Table of Contents

Published

Last Updated

Category

Tags

Contact

Other contents

節点・枝・葉の関係