数理解析研究所講究録 1325 巻 2003 年 221-226

221

MPR 束における「結び既約元」の数理的性質について-On mathematical properties of join-irreducibles in MPR-Lattices成嶋 弘
宮川 幹平
東海大学福岡短期大学

Abstract

With biological sciences such as taxonomy, cladistics and phylogeny as abackground, the principle of maximum parsimony also called Wagner Parsimony has beenmathematically formulated and then amathematical and algorithmic theory has beendeveloping. Recently, a clear method for the character-state minimization problem(Most-Parsimonious Reconstruction) Problem under linearly
called the First
ordered character-states has been presented by Hanazawa et al. (1995), Narushima
and Hanazawa (1997). From aphylogenetic point of view, Minaka (1993) has intrOduced apartial ordering on the set of MPRs to investigate the relationships among
the MPRs. Miyakawa and Narushima (1999) have shown that an MPR-poset induced by this ordering is acomplete distributive lattice. In lattice theory, acomceptof “join-irreducible” is very important, because the fundamental theorem for finite
distributive lattices states that the set of all order ideals of the subposet which consist of the join-irreducibles in finite distributive lattice , ordered by inclusion, islattice-.somorphic to . In this paper, we show some mathematical properties of-lattice.
join-irreducibles in a$\mathrm{M}\mathrm{P}\mathrm{R}$

$L$

$L$

$\mathrm{f}\mathrm{f}\mathrm{i}\dot{\mathrm{u}}\mathrm{t}\mathrm{e}\mathrm{M}\mathrm{P}\mathrm{R}$

1. 導入
近年, 系統分類学, 分子系統学等の各分野において, 対象となる種や分類単位の形質状態 (形態的もしくは遺伝子的な情報) から進化系統樹 (進化の道筋) を推定する問題が盛んに議論されている. この問題を大まかに言うと, その形質状態を実際に観察できる種の分) の集合力\leq 与えられたとき}こ,類単位 (操作的分類単位: Operational taxonomic
進化生物学的に適切と考えられる系統樹形と, 樹形上の内部分岐点に対応する仮想的分類う問題と考え) に適切な形質状態を復元すると単位 (Hypotheticalられる. またその手法としては, 何を「進化生物学的に適切」 と考える基準とするのかという点も含めて様々な手法が提案されており, 本論文ではこの中で最節約法に焦点を当てる.
」等
なお, 系統樹推定に関する進化生物学的議論について, より詳しくは文献 [12, 3, 13,を参照されたい.
ここで簡単に最節約法について説明する. 復元された系統樹において, 枝の長さとはその両端点に対応する分類単位の形質状態間距離 1 のことであり, 系統樹全体の長さとは各枝の長さの総和のことである. ここで最節約法とは, 「対立仮説の中で, 最も単純に形質分布を説明できる仮説を選択する」 という最節約原理に従い, 系統樹全体の長さが最小となる$\mathrm{u}\mathrm{n}\mathrm{i}\mathrm{t}:\mathrm{O}\mathrm{T}\mathrm{U}$$\mathrm{A}\mathrm{a}$$\mathrm{t}\mathrm{a}_{\mu}\mathrm{x}\mathrm{o}\mathrm{n}\mathrm{o}\mathrm{m}\mathrm{i}\mathrm{c}\mathrm{u}\mathrm{n}\mathrm{i}\mathrm{t}:\mathrm{H}\mathrm{T}\mathrm{U}$$11^{1}$

背景となる進化モデルや形質状態集合の定義が反映される. 例えば核酸塩基配列データのようにどのような変化も 1 ステツプで行える形質状態を扱う場合には ミング距離を, 形態学的形質によく見られるように, 離れた形質状態間の変化にはそれだけ多くのステツプカ 力 1 力 1 るような形質状態を扱う場合にはマンハッタン距離が代表的なものとして挙げられている. より複雑なモデルとしては, 各形質状態間の変換に確率的重みを付与したものなどがある.
1 この距離の定義には,$J\backslash$$\mathrm{i}$222

ように樹形や仮想的分類単位の形質状態を復元する系統樹推定手法である.

なお, そのよReconstruction)と呼ぶ.
:Most-Parsimonious

うな条件を満たす復元を最節約復元 (この問題は, 与えられた樹形の下での仮想的分類単位に対して, 最節約原理の下で最適な$\mathrm{M}\mathrm{P}\mathrm{R}$形質状態を求める問題と, 最適な樹形とその仮想的分類単位に対する形質状態を同時に求める問題, という 2 個の問題に分けて論じられている [1]. なお, 我々は前者を第 1 最節約復元問題, 後者を第 2 最節約復元問題と呼んでいる. 本論文では第 1 最節約復元問題について論じる.
第 1 最節約復元問題に関する研究は Farris[l] に始まり, Swofford and Maddison[10] を経て, Hanazawa et. a1.[2] によって数理的に厳密な問題の定式化がなされ, またそれと共与えられた樹形のもとでの最節約復元を全て再帰的に列挙する簡明なアルゴリズム及ひその時間計算量に関する解析が与えられている. また, [10] では, 対象としている生物に,群の共通祖先 (系統樹の根となる分類単位) を仮定するとき, 系統樹解析において意味のあると思われる復元として, 以下の二つが提案された.

ACCTRAN 復元形質状態の変化ができるだけ根の近くで生じるように形質状態を設定する (形質変換を促進する:Accelerated Transformation). 形質進化の逆転 2 回数は最大化され, 逆に形質の収斂 3 は最小化される,

DELTRAN 復元形質状態の変化ができるだけ末端近くで生じるように形質状態を設定す

る (形質変換を抑制する:Delayed Transformation). 形質の収斂回数は最大化され,逆に形質進化の逆転は最小化される.
これらの復元に関して, 数理的な立楊からもその特徴が解析されている [7, 8, 5].
なお, 与えられた系統樹の MPR は上記で挙げた ACCTRAN, DELTRAN だけではな
く, 一般的には樹形の頂点数について指数関数的に存在する. これら複数の MPR は, それぞれ形質進化に関して異なる背景の仮定 4 を持っていると考えられており, 各 MPR の数学的特徴づけと進化生物学的特徴づけの対応が試みられている.
また三中 [12] は, 各 MPR の比較や MPR 全体の特徴を調べるため, MPR 全体集合にある半順序を導入した. この順序による MPR 半順序集合 (MPR-poset) ?ま, 数学的に見ると完備な分配束 (MPR 束) になっていることが証明されており [4], そのため, MPR 全体集合に対して, 束論的なアプローチが可能になった. 本論文では, MPR 束において, 束論的に重要な要素である結ひ既約元を数理的に特徴づけ, 結ひ既約元を構築するためのアルゴリズムを示す.

2. 準備
外点に付値されている樹形が与えられたとき, その木の長さを最小化するような内点への付値を定める問題を第 1 最節約復元問題と呼ぶ. まず, この問題を以下のように定式化する.
2 逆転 (reversal) とは, 一旦変化した形質状態がその子孫で再ひ元の状態に戻るといった, 一般に言う先祖がえり現象のことを指す.
3 収斂 (convergence) とは, 遺伝的に異なる複数の生物が, 類似する形質を個別に進化させることを言う.
4 例えば, ある部分木においては進化が促進又は逆に抑制されるなど.

223 223を単純な無向木とする. $V(T)$ を $T$ の頂点集合, $V_{O}(T)$ を外点 (次数 1 の頂点) 集合, $V_{H}(T)$ を内点集合, $E(T)$ を $T$ の辺集合とする. 混乱する恐れの無い限り, これらを$E$ と書く.
またを実数集合もしくは整数集合とする. ここで外
単にそれぞれ $V,$としたとき, この木構造を我々は el-木 ( $el$-tree) と呼ひ,点に対する付値関数を :を整数集合とする. 本論文においての結果は$T=(V, E, \sigma)$ と書く. なお, 以下の例ではが可算的でなければ成り立たないことに注意されたい. el-木 $T$ が与えられたとき,(に定義域を制限した ) が と等しいような $T$ の各頂点への付値関数 : $Varrow\Omega$ を$T$ の復元(reconstruction) と呼ぶ. ここで 1 節で述べた進化生物学的議論との関係を考えがが仮想的分類単位 (HTU) の集合,が操作的分類単位 (OTU) の集合,
ると,が各仮想的分類単位に対する形質状態(操作的分類単位に対して) 観測された形質状籐,$T$ に復元が与えられたとき, 各辺 $e\in E$次に,el木の仮説, にそれぞれ対応している.
を $\ell(e|\lambda)=|\lambda(u)-\lambda(v)|,$ $e=\{u, v\}$ と定義する. また復元 が与えら{こ対して長さ$T$れたときの の長さを各辺の長さの総和と定義する. 即ち, $L(T| \lambda)=\sum_{e\in E}\ell(e)$ . さらに,$T$$\Omega$$V_{O},$ $V_{H},$$V_{O}arrow\Omega$$\sigma$$\Omega$$\lambda|V_{O}$$\Omega$$\lambda$$\lambda$$V_{O}$$\sigma$$V_{H}$$V_{O}$$\sigma$$\lambda$$\lambda$$\lambda$$l(e|\lambda)$$T$の長さの最小値 $L^{*}(T)$ を以下のように定義する:$L^{*}(T)= \min$

ここで,{$L(T|\lambda)$となるような復元$L(T|\lambda)=L^{*}(T)$|\lambda は$T$

上の復元 }.

を $T$ 上の最節約復元 (以 T では $MPR$ と書$\lambda$.

り$\nearrow\ovalbox{\tt\small REJECT} \text{る値の集_{}\square }^{\mathrm{A}}\{\lambda.(u)|\lambda\in \mathrm{R}\mathrm{m}\mathrm{p}(T)\}\text{を}u\not\subset)\mathrm{M}\mathrm{P}\mathrm{R}-\mathrm{a}\mathrm{e}\underline{\Leftrightarrow}(MPR- set)\text{と呼ひ},\acute{S}_{u}\text{と}\check{\ovalbox{\tt\small REJECT}}\grave{\text{く}く})\text{と呼ひ},T_{-}\mathrm{h}\text{の}\mathrm{M}\mathrm{P}\mathrm{R}\text{全}ffi\text{の集_{}\mathrm{f}=}^{\mathrm{A}}\text{を}\mathrm{R}\mathrm{m}\mathrm{p}(T)\text{と_{}\Xi}\geqq\langle.\text{ま}=,\text{各}\mathrm{M}\mathrm{P}\mathrm{R}\emptyset\check{:}\Re,\mathrm{f}_{|\Xi uC^{\backslash }\Phi}$与えられた el-木 $T$ について, ある頂点 を根 (root) と定めることで, 根付き el-木も自然に定義できる. 根付き -木上において, 頂点 が の親であるとき, $u=p(v)$ と書く. また, 根でない外点を特に葉 (leaf) と呼ぶ. ここで注意として, その定義から明らかなように MPR は根に依存しない. 根を定めるのは前節で述べたように, 対象とする操作$T^{(r)}$

$r$

$u$

$\mathrm{e}1$$v$

的分類単位に対して共通的な祖先となる分類単位を仮定するという進化生物学的観点からか,MPR を決定するためのアルゴリズム的必要もしくは (より純粋な数理的問題として)性からかのどちらかである.
$\mathrm{I}=\{I_{i}|1\leq i\leq n\}$$I_{i}$

を$\Omega$

上の (多重) 閉区間族としたとき,I に含まれる全ての閉区間の両端点を以下のように昇順に並べたとする.
$x_{1}\leq\ldots\leq x_{n}\leq x_{n+1}\leq\ldots\leq x_{2\mathrm{n}}$.と $x_{n+1}$ を閉区間族 の中間 2 点 (median two points) と呼ひ, その列
このとき,と書く. また, この中間 2 点を端点とす
もしくはを med2
る閉区間 $[x_{n}, x_{n+1}]$ を, 閉区間族 I の中間区間 (median interval) と呼ひ, mcdと書く.
もしくは上の閉区間 $I(u)$ を以下のよう
次に, 根付き -*\emptyset 本体に属する各頂点 l こついて,$\langle x_{n}, x_{n+1}\rangle$$\mathrm{I}$$x_{n}$$\mathrm{m}\mathrm{e}\mathrm{d}2\langle I_{i}|1\leq i\leq n\rangle$$\langle I_{1}, I_{2}, \ldots, I_{n}\rangle$$\langle I_{1}, I_{2}, \ldots, I_{n}\rangle$$\mathrm{m}\mathrm{e}\mathrm{d}\langle I_{i}|1\leq i\leq n\rangle$$\Omega$$u$$\mathrm{e}1$に再帰的に与える:$I(u)=\{$$[\sigma(u), \sigma(u)]$med(I $(v)|u=p(v)\rangle$( $ul^{*}:F^{\text{のと}}$ き) ,(それ以外).としたときのる区間列を表すものとする. 以下でも同様の表現を用いる. この閉区間 $I(u)$ を

但し,$\langle I(v)|u=p(v)\rangle$

は,$u$の子を$v_{1},$$v_{2},$$\ldots,$$v_{m}$なの特性区$\langle I(v_{1}), I(v_{2}), \ldots, I(v_{m})\rangle$$u$

224

間, また$I$

を $T$ 上の特性区間写像と呼ぶ, これらは第 1 最節約復元問題に関する一連の論文のキーコンヤプトである.
次の結果は el-木 $T$ に対して,の最小長と MPR 全体の集合を特徴づける, 第 1 最節約復元問題の基本定理と呼ぶべき定理である. なお再度の注意として, $T$ の根 をどのよ
$T$$r$

うに選んでも,$T$の最小長そのものの値や MPR 全体の集合には影響しない.

定理 1(花沢-成鴫-三中 [2]) $T$ を根付き el-木とし,において,$T^{(r)}$の $MPR$ であるための必要十分条件は各内点 $u$$\lambda$$I(u)$

を $T$ 上の復元とする.

$\lambda$

が $T$ 上( が根である) ,(それ以外の内 ).
$u$$\lambda(u)\in\{$$med\langle[\lambda(p(u)), \lambda(p(u))], I(v)|u=p(v)\rangle$$r^{\mathrm{f}}\iota\tau\backslash 5$を満たすことである.
なお, 以下では任意の $x\in S_{p(u)}$ [こ対して med([x, ], $I(v)|u=p(v)\rangle$ を $S_{u}|x$ と書く.
こで, 本論文での定理の証明に有用な命題を次に引用する.
$x$を $T$ 上の特性区間写像としたとき,
命題 2(宮川-成嶋 [4]) $T$ を根付き -木,とその子 に対して, 次の 3 通りのいずれか 1 つのみが成立する.
$el$

$I$

$T$

この頂点

$v$

$u$

1. $\min S_{\mathrm{u}}<\min I(v)$ ,2.

$S_{u}\subseteq I(v)$3.

$\mathrm{m}\mathrm{a}_{d}\mathrm{x}I(v)<\max S_{u}$,.

ここで, $V$ 上の弧集合 $A(E)$ を以下のように定義する : $u,$ $v\in V$ に対して, $(u, v)\in A(E)$となるのは, $\{u, v\}\in E$ であり, かつ, $T$ を $u=p(v)$ となるような任意の頂点で根付けしが命題 2 の 1. を満たすときである. このとき, MPR を以下のように特徴づけすることもできる :たとき,$u,$ $v$

命題 3el-木 $T=(V, E, \sigma)$ の復元$\{u, v\}[]_{\acute{\mathrm{L}}}\mathrm{k}^{\backslash }1^{\mathrm{a}}\text{て}$$\lambda$

が $T$ の $MPR$ であるための必要十分条件は, 各辺 $e=$,$\{$$\lambda(u)\leq’\backslash (v)$$((u, v)\in A(E)$ 。’ よ、,$\lambda(u)\geq\lambda(v)$$((v, u)\in A(E)$ のとき),$\lambda(u)=\lambda(v)$$((u, v),$ $(v, u)\not\in A(E)$ のとき).

を満たすことである.

3. MPR 束と結ひ既約元MPR 全体集合 Rmp(T) 上の二項関係 を三中 [3] に従って以下のように定義する : 任とは, 任意の頂点 u}こおいて $\lambda(u)\leq\mu(u)$ が成り立つこに対して,意の MPRとである. このとき, 明らかに は MPR 全体集合上の半順序である. この順序 によって誘導された半順序集合 (MPR-poset) に関して, 以下のような束論的特徴づけがなされ$\leq$$\lambda,$$\mu$$\lambda\leq\mu$$\leq$$\leq$

225

定理 4(宮川-成嶋 [4]) el-木 $T$ において,$MPR$ -poset $(Rmp(T), \leq)$ は完備分配束である.と交わり
MPR 全体集合上の束演算 (結ひを任意の頂点とするとき,とする.
任意の MPR
ここで,$(\vee)$$\lambda,$$(\Lambda)$) は以下のように定義される

$u$

$\mu$

$(\lambda\vee\mu)(u)$$= \min\{\lambda(u), \mu(u)\}$$(\lambda\Lambda\mu)(u)$$= \max\{\lambda(u), \mu(u)\}$

なお本論文であつかう範囲では が可算であるため, MPR-poset は有限である. 有限分配束において, 重要な概念のひとつが既約 (irreducible) の概念である. ある最小元でない元 が結ひ既約 (join-irreducible) であるとは, 他の任意の二つの元の結ひ演算 (V) によってを表現できないことを言う. 交わり既約も同様である. 有限分配束の基本定理として,と $J(P)$
有限分配束 t こおいて, ある有限半順序集合 $P$ が順序同型を除いて唯一存在し,$P$が束として同型であることが良く知られている. この とは の結ひ既約 (もしくは交わり既約) 元の集合からなる部分半順序集合 (と順序同型) である. つまり, 結ひ既約 (もしくは交わり既約) 元とは有限分配束の生成元ということになる.
$\Omega$

$x$

$x$

$L$

$L$

$L$

次節において,MPR 束における結ひ既約元を構築する為のアルゴリズムを示す.

4. 主定理とを結ぶ $T$ 上の\nearrow
を, $V$ 上の頂点
el-木 $T=(V, E, \sigma)$ において, $V$ 上の関係
スの任意の辺 $e=\{u.v\}’\}$ こついて, $(u, v),$ $(v, u)\not\in A(E)$ であるとき $x\sim y$ , と定義すによる $V$ の同値類を
は $V$ 上の同値関係である. ここで,る. このとき, 明らかに$i\in[1, k]$ について, $u,$ $v\in B_{i}$の定義より, 任意の MPRとする.
であるなら $\lambda(u)=\lambda(v)$ である. よって, $u,$ $v\in B_{i}$ ならば Su=S。が成り立つ. そこで,
$S_{B}:=S_{u}$ (但し u\in B板蟲舛垢. ここで, 任意の $i\in[1, k],$ $x \in(\min S_{B}, \max S_{B}]::$ [こを以下のように定義する :対して, $T$ の復元$x$$\sim$$y$$\mathrm{P}$$\sim$$\sim$$B_{1},$ $B_{2},$$\cdots,$$A(E\cdot)$$B_{k}$$\lambda,$$\lambda_{i,x}$1.

$B_{j}$

上の任意の点$r$を根とする , 根付き el-木を構成する.

2. $u:=r,$ $\lambda_{i,x}(u):=x$ と定める.
3,$u$の子$v$について,$v$が葉であれば停止する. そうでないとき,$\mathrm{m}\mathrm{e}\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{n}\langle\lambda(u), \min S_{v}, \max S_{v}\rangle$$\lambda_{i,x}(v):=\{$$((u, v)\in A(E)$ のとき),$\min S_{v}$$((v, u)\in A(E)$ のとき),$\lambda(u)$$((u, v),$ $(v, u)\not\in A(E)$ のとき).と定める.

4. $v:=u$ として, 3. を再帰的に繰り返す.
このとき, 次の命題が成り立つ.

226

命題 5el-木 $T=(V, E, \sigma)$ において,$V$上の関係$\sim$による同値類を$B_{1\}}B_{2},$ $\cdots,$$B_{k}$とする.

$i,j \in[1, k])x\in(\min S_{B}\dot{.}, \max S_{B_{\mathrm{i}}}],$ $y \in(\min S_{B_{j}}, \max S_{B_{j}}]$ としたとき,$i=j$ かつ $x=y$

は,$\lambda_{i,x}=\lambda_{j,y}$と必要十分である.

最後に, 本論文における主定理を述べる.

定理 6el-木 $T=(V, E, \sigma)$ において, $T$ の復元 が $MPR$ 束 $(Rmp(T), \vee, \Lambda)$ の結ひ既約元としたとき, あによる同値類をである為の必要十分条件は, $V$ 上の関係となることである
.
が存在して
,
$x\in(\minS_{B}\dot{.},\max
S_{B}\dot{.}]$
る $i\in[1, k],$$\lambda$$B_{1},$ $B_{2},$$\sim$$\cdots,$$B_{k}$$\lambda=\lambda_{i,x}$

References[1] J. M. Farris, Methods for computing Wagner trees, Systematic Zoology$\mathrm{v}\mathrm{o}\mathrm{l}.19,$$\mathrm{p}\mathrm{p}.83-92$,1970.
[2] M. Hanazawa, H. Narushima and N. Minaka, Generating most parsimonious reconstructions on atree: ageneralization of the Farris-Swofford-Maddison method, Discrete Applied

Mathematics$\mathrm{v}\mathrm{o}\mathrm{l}.56,$$\mathrm{p}\mathrm{p}.245-265,1995$.

[3] N. Minaka, Algebraic properties of the most parsimonious reconstructions of the hypothetical.
ancestors on agiven tree, Forma$\mathrm{p}\mathrm{p}.277-296,1993$$\mathrm{v}\mathrm{o}\mathrm{l}.8\mathrm{n}\mathrm{o}.2,$[4] K. Miyakawa and H. Narushima, Lattice-theoretic properties of MPR-posets in phylogeny,投稿中.

[5] K. Miyakawa and H. Narushima, On mathematical properties of ancestral cbaracter-state
reconstructions under the delayed transformation optimization, 投稿中.
[6] H. Narushima and M. Hanazawa, Amore efficient algorithm for.
Discrete Applied Mathematics$\mathrm{v}\mathrm{o}\mathrm{l}.80,$$\mathrm{M}\mathrm{P}\mathrm{R}$problems in phylogeny,$\mathrm{p}\mathrm{p}.231-238,1997$[7] H. Narushima and N. Misheva, On characteristics of ancestral character-state reconstructions,
under the accelerated transformation optimization, Discrete Applied Mathematics
pp. 195-209, 2002.
$\mathrm{v}\mathrm{o}\mathrm{l}.122$[8] H. Narushima, On extremal properties of ACCTRAN reconstructions in phylogeny, preprint.

[9] D. F. Robinson, Extending afunction on a graph, Discrete MatheIIlatics 6 (1973) 89-99.
[10] D. L. Swofford and W. P. Maddison,parsimony, Mathematical$\mathrm{R},\mathrm{e}\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{t}\mathrm{r}\mathrm{u}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{n}\mathrm{g}$$\mathrm{B}\mathrm{i}\circ \mathrm{s}\mathrm{c}_{J}\mathrm{i}\mathrm{e}\mathrm{n}\mathrm{c}.\mathrm{e}\mathrm{s}\mathrm{v}\mathrm{o}\mathrm{l}.87,$

ancestral character states urider Wagner.

$\mathrm{p}\mathrm{p}.199-229,1987$[11] 馬渡峻輔編著, 動物の自然 fi–ae 代分類学の多様な展開, pp.183-267, 北海道大学図書刊行会,

1995.

[12] 三中信宏, 組合せ論的視点から見た系統推\not\in -- 節約法と離散数学の接自然誌研究報告, 第 2 巻第 2 号 pp.83-98,

1993.

[13] 三中信宏, 生物系統学, 東京大学出版会, 1997.

$\mathrm{f}\mathrm{i}\iota\iota$–, 千葉中央博物館