ボトムアップ手法を用いた系統樹構築の近似アルゴリズム(計算機科学の理論とその応用)

ボトムアップ手法を用いた系統樹構築の近似アルゴリズム

前村一哉

(Kazuya Maemura)*

小野廣隆

(Hirotaka Ono)

\dagger

定兼邦彦

(Kunihiko

Sadakane)

\dagger _山下雅史

_{(Masafumi Yamashita)}

\dagger

* _{九州大学大学院システム情報科学府}

DePt.

of Electrical

Engineering and Computer

Science,

Kushu University

\dagger

_{九州大学大学院システム情報科学研究院}

Dept.

of

Electrical

Engineering and Computer Science, Kushu University

概説

系統樹は異なる生物種が進化の過程において, どの ように分岐したかを木として表したものである. 系統 樹においてラベル付けされた葉は生物種に, 根はすべ ての種の共通祖先に, 内部節点は葉となる種の共通祖 先に対応している. 本稿では, 葉となる種の集合$S$ と3つの種からなる 3点系統樹の集合$T$を入力として与えられたとき, $T$ に含まれるできるだけ多くの 3 点系統樹の祖先. 子孫 関係を満たす木を構築する問題を扱う. この問題は

NP

完全問題であることが証明されており, 近似アルゴリ ズムの立場から研究されている $[2,3]$

.

本稿では、既存 の近似アルゴリズム [3] を改良したアルゴリズムを提 案し, 提案したアルゴリズムと元のアルゴリズムに関 する定理の証明を行う.

1

はじめに

現存するすべての生物種はある共通の祖先から進化 しており. それらの間には何らかの進化的な関係があ ると考えられている. 系統樹とは, 進化の過程におい て共通祖先からどのように分岐してきたかという生物 種間の進化的関係を木構造で表現したものである. 系 統樹は根付き非順序木であり, その木において一意に ラベル付けされた葉は

(現存する)

生物種に, 根はす べての生物種の共通祖先に, 内部節点は葉となる生物 種の祖先となる種に対応している. 図1は系統樹の例 である(http://www.christiananswers.net/home 上 tml より). 図 1: 系統樹の例 数多く存在する既知の種に対する系統樹を直接考え るのは現実的ではない. そのため, 一般的には数種類

(3,4

種類

)

の種からなる部分的な系統樹を用いて全体 の木の構築を考える. 著者の研究では, 3種類の生物 種からなる 3 点系統樹と呼ばれるものから木を構築す る問題を取り扱う.

2

準備

本節では準備として. 問題の入力となる3点系統樹 と 3 点系統樹を入力とした系統樹構築の間口について 述べる.

21

3

点系続樹 $i,$$j,$$k$ を種とすると, 3点系統樹は図2のような 木で表すことができる. この木は $\{i, j\}<\{i, k\}$ や

$\{i, j\}<\{j, k\}$ のように表記される.

_{このとき拡}

$j$

}

は種$i$ と $j$ の LCA(共通祖先で最も根から遠い祖先,

Lmvest

$Comm\sigma nAnce\epsilon tor$)_{にあたるノードを表して}

おり. 同様に$\{i, k\}$ は種$i$ と $k$の

LCA

にあたるノード

を表している. $\{i, j\}<\{i, k\}$は$i$ と $j$の

LCA

は$i$ と

$k$_の

LCA

の正統な子孫であることを示している. _ま

た, $\{i, j\}<\{i, k\}$や$\{i, j\}<\{j, k\}$ は$(\{i\cdot,j\}, k)$ とも

表記されることがある. 本稿では, これ以降の3点系

統樹の表記は $(\{i, j\}, k)$ _{を用いることにする}.

Problem)$fMCTT(the$

_Maximum

_Consensus

_Tree

from

rooted

Triples problem) と呼ばれ, 近似アルゴ

リズムの立場から研究されている. この問題では, い かに上手く制約を満たす木を構築するかが重要となる.

3

既存の研究

本節では既存の研究の論文[3]において提案されてい る近似アルゴリズムについて述べる. 次節では, 本ア ルゴリズムを改良したアルゴリズムについて説明する. 図2: 3点系統樹の例

22

系統樹構築に関する問題

系統樹を構築する問題の入力として, 一般的には$S$ と $T$が与えられる. $S$は生物種の集合を, $T$_は$S$_の3

つの種からなる 3 点系統樹の集合を表している

(以降

は $|S|=n,$$|T|=m$ とする). 3 点系統樹における祖 先. 子孫関係” は木を構築するための ‘嘲約” と考える ことができる. 具体的に図

2

のような

3

点系統樹が$T$に含まれる1 つの要素として与えられているときを考える

.

この場 合, $i$ と _$i$は同じ部分木の葉にならなくてはならない

.

これは, もし$i$ と $j$ が異なる部分木の葉ならば. $i$ と $j$ の

LCA

_{は根ということになり. 図のような祖先. 子} 孫関係を満たさなくなるためである

.

著者の研究で扱う問題は, $S$ と $T$が与えられたとき に$T$

に含まれる制約を満たす木を構築するというもの

である. $T$

のすべての制約を満たす木を構築できるか

という決定問題は.

多項式時間で解けることが既に示

されている [1]. また. $T$ _{の制約をできる限り多く満たすような木} を構築する問題も研究されており, これは

_NP

完全 問題であることが証明されている $[2, 3]$

.

_この問題

はMICT(the

Maximum

_Inferred

Consensus

Tree

3.1

アルゴリズム

_Best

_{Pair Merge First}

アルゴリズム

Best Pair

Merge

First(

以降

PM

と書

く)の流れを以下に示す. 初期集合として, それぞれ $n$種類の具なる種に一意にラベル付けされた$n$個の節 点(木) の集合$\tau$がある. 集合$\tau$は 1っの木のみを含む 集合になるまで, 2 つの木を選んで結合する. 定義31 $V(t_{i})$は木$t_{i}$ のもっ葉(種)の集合を表す. このアルゴリズムでは, 結合する2つの木を遡ぶ 基準として excore(V$(t_{i}),$$V(t_{f})$) という関数を用い る. ここで$t_{i},t_{j}\in\tau$ とする. 各々の反復で最大の $e_{-}gcore(V(t_{i}), V(t_{j}))$ _{となるような 2 つの木を遷ぴ, 結} 合する. アルゴリズム

_PM

は$e_{-}s\omega re$が最大になるよ うな 2 つの木を選んで結合することによって, 満たす 3 点系統樹の数ができるだけ多い木をヒューリスティッ クに構築している. アルゴリズムの詳細を表 1 に示す. 定義 32

$\bullet$ $w(V(t_{i}), V(t_{j}))$

:

$(\{i., j\}, x)$ となる3点系統樹の

数. ただし, $i\in V(t_{i}),$ $j\in V(t_{j}),$ $x\in S\backslash \{V(t_{i})\cup$

$V(t_{j})\}$ とする.

.

Algorithm

Best Pair

Merge

First

(1)$\tau=\{t_{l}|1\leq l\leq n\}$

.

$t_{l}$は葉$l$ だけを含む木 (2)$while|\tau|>1$ do (2-1) $\tau$から $e_{-}score(V(t_{j}), V(t_{j}))$ が最大になる ような$t_{i}$ と $t_{j}$ を選択 (2-2)共通祖先となる内部節点を加えて$t_{i}$ と $t_{j}$ を 結合して新たな木を構築 endwhile (3)構築された木を返す

.

$p(V(t;), V(t_{j})):t_{i}$ と$t_{j}$を選んだ時に$(\{i, j\}, x)$に

反する 3 点系統樹の数. より具体的には$(\{i, x\},j)$,

$(\{j, x\}, i)$ となる3点系統樹の数. ただし, $i\in$

$V(t_{i})$

.

$j\in V(t_{j})$

.

$x\in S\backslash \{V(t:)\cup V(t_{j})\}$ とする.

$\bullet$ $t(V(t_{i}), V(t_{j})):(\{i, j\}, x)$となる 3 点系統樹の数.

ただし$i\in V(t_{i}),j\in V(t_{j}),x\in S\backslash \{i, j\}$ とする.

$e_{-}s\omega re$ として, 以上の3つの関数を組み合わせた6つ

の関数を定義する. 分子に$w(V(t_{i}), V(t_{j})),$ $w(V(t_{i})$,

$V(t_{j}))-p(V(t_{i}), V(t_{j}))$ を用いたものをそれぞれ

if-penaltyがFalfie,

_Ihle

であると呼ぶ. また, 分母に

1.

$w(V(t_{i}), V(t_{j}))+p(V(t_{i}), V(t_{l})),$ $t(V(t_{1}), V(t_{j}))$

を用いたものをそれぞれRatio-tyPeが$0,1,2$ である

と呼ぶ. 関数$e_{-}score$ をまとめたものが表2である.

この表では$w(V(t_{i}),V(t_{j}))$ を$w,$ $p(V(t_{i}), V(t_{j}))$ を$p$

.

$t(V(t_{i}).V(t_{j}))$ を$t$ と表記している.

4.1

アルゴリズム

Best

Pair Merge

with

Re-construction

前節で述べたアルゴリズム

PM

は木の集合から関数

e-score

を最大にする 2 つの木を選び, 結合して新し い木を構築するものであった. そのため, 初めに 2 つ の木$t_{x}$ と $t_{y}$が結合して次に$t_{z}$が結合するときに. こ の順序で結合した木が最も多くの3点系統樹を満たす とは限らない. つまり, アルゴリズム

PM

において図 3(1) のような木になるときに図 3(2)や(3)のような木 に構築した方が満たす 3 点系統樹が多い場合があると 言える. 本稿で提案するアルゴリズムは

PM

において, この点を考慮したアルゴリズムである. 図3: $t_{x},t_{y},$$t_{z}$が結合する木の例 表2: 関数$e_{-}\epsilon core(V(t_{i}), V(t_{j}))$ の組合せ表

論文においては具体的な近似比と時間計算量は述べ

られていない. この論文の著者が行った計算機実験で は, 実験のインスタンスの7割以上で, 論文

[2]

で提 案されている2 っの近似アルゴリズムよりも良い結果 となっている. また, アルゴリズム

PM

において関数 $e-9care$を計算する回数は$O(n^{l})$回であるので, 時間 計算量はおよそ$O(mn^{8})$であると言える.

4

提案手法

本節では, 前節で紹介したアルゴリズム

PM

を改良 したアルゴリズムについて述べる. また. 著者が行っ たアルゴリズム

PM

と本節のアルゴリズムを比較する ための実験およびその結果, さらに定理とその証明に ついて述べる. 定義 41 関数

Sat

$(t_{1})$ を木$t_{i}$が満たす入力$T$に含まれ る3点系統樹の数とする.

アルゴリズム

Best

Pair

Merge

_with

k\mbox{\boldmath $\varpi$}戯

rllc-tion(

以降

PMR

を書く

)

の流れを以下に示す. 初期集 合として, それぞれ$n$種類の異なる種に一意にラベル 付けされた$n$個の節点

(

木

)

の集合$\tau$がある. $\tau$が1つ の木のみを含むまで 2 つの木を選んで結合する点と木 を選ぶ基準として関数

e-score

を用いる点は

PM

と同 じである. アルゴリズムの任意の反復で$e_{-}\epsilon core$を最大にする

木がちとちであるときを例に考える.

$t_{t}$ は2つの木

蘭と碗が結合してできた木とする

.

同様に$tj$ は2つ の木$t_{j1}$ &tj2 が結合してできた木とする. このとき, 図4の各々の木の

Sat

の値を計算する. この 5 つの中 で最大の

Sat

の値となる木の形に木を再構築する(PM では. すべてちの形に構築されることになる

).

アル ゴリズムの詳細を表 3 に示す.

42

実験結果の比較

任意の$S$ と $T$を入力として, アルゴリズム

PM

で構 築される木を$T_{PM}$,

PMR

で構築される木を$T_{PMR}$, 最適解の木を$T_{\varphi l}$ とする.

図4: $t_{a},t_{\beta 1},t_{\beta 2},t_{\gamma 1},t_{\gamma 2}$

.

Algorithm

Best

Pair

Merge

with

Reconstruction

(1)$\tau=\{t_{l}|1\leq l\leq n\}\cdot t_{l}$は葉$l$ だけを含む木

(2)$while|\tau|>1$ do

(2-1) $\tau$ から $e-9\infty re(V(t_{i}), V(t_{j}))$が最大になる

ようなちとちを選択

(2-2)

Sat

$(t_{\alpha}),$$Sat(t_{\beta 1}),$ $Sat(t_{\beta 2}),$$Sat(t_{\gamma 1})$

,

Sat

$(t_{\gamma 2})$ の値を計算する

(2-3)

Sat

の値が最大になる木に構築する

endwhile

(3)構築された木を返す

表3: アルゴリズム

Bst Pair

Merge with$R\propto ont$

tnlC-tion

アルゴリズム

PM

と

PMR

の構築する木の満たす 3 点系統樹の数を比較するために, 実装してその実験結 果を比較した. $n=15$ で固定し, $m=50,100,200$,300 で行った. $0$から14までの整数を種としてランダムに 発生させ, その 3 つずつを組として 3 点系統樹を作成 した. 各々の$m$で乱数の種を変えて10回ずつ行った. 表4と表5は実験結果をまとめたものである.

PMOI

は. アルゴリズム

PM

で$e_{rightarrow}\epsilon core$は

if-penalty

が

False

で$Mti\triangleright type$が1のときの結果であることを表して いる. 表4の数値は各々の結果の $\frac{Sat(T_{ort})}{Sat\{T_{PAl})}$ または $\frac{Sa\ell(\tau_{ru})}{Sat(T_{PktR})}$ の平均値を示している. 表5の数値は各々 の結果の$\frac{Sol(T_{\Phi\#})}{Sal(T_{PM})}$ または$\frac{s_{a}\ell(\tau_{\infty\iota})}{Sat\langle T_{PMR})}$ の最悪の値を示 している.

43

定理とその証明 定理4.1 アルゴリズム

_PM

と

_PMR

における木の結合 は, 集合$\tau$に含まれる木に対する関数

e-score

の値の みで決まる. また. $e$-gcore

は木ちが持つ葉

(

種

)

から 表4: 実験結果の比較

(

平均値

)

表 5: 実験結果の比較

(最悪値)

計算される. 任意の入力$S,$ $T$において,

Sat

$(T_{PM})\leq$ $Sat(T_{PMR})$が成り立っ. 証明 アルゴリズム

_PMR

の任意の反復において $e_{-}score(V(t_{1}), V(t_{j}))$が最大となるとき, 以下の 2 通 りに場合分けができる. (i) 再構築が行われない場合 この場合, 図 4 の

t

。が構築される

.

これは

PM

と 同じなので,

_Sat

$(T_{PM})=Sat(T_{PMR})$ である. (n) 再構築が行われる場合

$V(t_{\alpha})=V(t_{\beta 1})=V(t_{\beta 2})=V(t_{\gamma 1})=V(t_{\gamma 2})$は明

らか. これより木の再構築後の反復では, $e$-scofe の

引数は再構築が行われても変わることはない.

これよ り, $T_{PM}$ と $T_{PMR}$は

t

_{。が再構築されている部分のみ}

が異なっている.

Sat

$(T_{PM})$ と

Sat

$(T_{PMR})$の大小関係は再構築された 部分木の満たす 3 点系統樹によって決まる. 再構築が行 われる場合には, その部分木の満たす

3

点系統樹の数

は

Sat

$(t_{\alpha})$ よりも多いので,

Sat

$(T_{PM})<Sat(T_{PMR})$

となる.

$(i),(\vec{n})$ より,

Sat

$(T_{PM})\leq Sat(T_{PMR})$が成り立っこ

5

まとめと今後の課題

本稿では系統樹と3点系統樹. 系統樹構築の問題に

っいて簡単に述べた. そして, 既存の研究のアルゴリズ

ムであるアルゴリズム

Baet Palr

Merge

First

を元にし

たアルゴリズム

Best Pair Merge

wiht

Reconstnuction

を提案し, 実験結果の比較と定理の証明を行った.

今後の課題としては, 本稿で提案したアルゴリズム

の改良が挙げられる. また, 新たなアルゴリズムを考

案してその考察, 解析などを行うことも挙げられる.

参考文献

[1] A.V.Aho, _{Y.Sagiv, T.G.Szymanski and J.D.Ullman,}

“Inferring a tree from lowest

common

ancestorswith

an

application tothe optimizationofrelationalexpre ト

sions”,

SIAM

Joumal

_of

Computing, Vol.10, No.3,

pp.405-421, 1981.

[2] L.Gasieniec, J.Jansson, A.Lingas and

A.\"ostUn,

“On

the Complexityof

Constructing

Evolutionary${\rm Re} ae$

,

Journd

_of

Combinatorial

$Optimizat\dot{w}n$, Vo1.3, pp.

183.

197,

1999.

[3] B.Y.Wu, “Constructing theMaximum Consenm18

Ttee

from RootedTtiples”,Joumal

_of

Combinatorial