数理解析研究所講究録1093 巻 1999 年 57-61

57

On Extremal Problems of MPR-posets$\Pi$

宮川幹平 (Miyakawa Kampei)
成嶋弘 (Narushima Hiroshi)

東海大学大学院
東海大学短期大学部

A mathematical theory for the subject on ancestral character-state reconstructions underthe maximum parsimony in phylogeny has been developing [1-9]. In this paper, we show
some extremal properties of-version MPR-posets, particularly, the lattice-theoretic
properties of those posets.
We use the notations in $[1, 4]$ . Let $T=(V, E, \sigma)$ be any undirected tree whose endnodes
are evaluated by a weight function :, where expresses the linearly orderedcharacter-states. From the viewpoint of enumeration, let denote the set of non-negativeintegers.
is the set of nodes,
is the set of endnodes which are nodes of degree one,is the set of internal nodes, andis the set of branches. Note that $V_{O}\cup V_{H}=V$and. We call this tree an -tree. For an -tree , we define an assignment:
such that(the restriction of to ), whereis called a state ofunder . This assignment is called a reconstruction on an -tree . For each branch
in of an -tree with a reconstruction , we define the length $l(e)$ of branch $e=\{u, v\}$by. Then the lengthof an -tree under the reconstruction is thesum of the lengths of the branches. That is, $L(T| \lambda)=\sum_{e\in E}l(e)$ . Furthermore, we define
the minimum length $L^{*}(T)$ of by$\sigma(r)$$V_{O}arrow\Omega$$\sigma$$\Omega$$\Omega$$V$$V_{O}$$E$$V_{H}$$V_{O}\cap V_{H}=\emptyset$$\lambda$$el$$Varrow\Omega$$T$$\mathrm{e}1$$\lambda|V_{O}$$\lambda$$V_{O}$$=\sigma$$\lambda(u)$$\lambda$

$u$

$T$

$\mathrm{e}1$

$E$

$T$

$\mathrm{e}1$$e$$\lambda$$|\lambda(u)-\lambda(v)|$$L(T|\lambda)$$T$$\mathrm{e}1$$\lambda$$T$$L^{*}(T)= \min${$L(\tau|\lambda)|\lambda$

is a reconstruction on$T$}.

Note that $L^{*}(T)$ is well-defined. A reconstruction such that $L(T|\lambda)=L^{*}(T)$ is calleda most-parsimonious reconstruction (abbreviated to MPR) on . Note that generally an-tree has more than one MPR. We denote the set of MPRs on by. For eachnode in , the setof states of under such thatis$MPR$
called the-set of and written as . The algorithms to get $L^{*}(T),$, andare given in $[1, 4]$ . See $[1, 4]$ for details.
For a given -tree $T=(V, E, \sigma(r))$ , we define a rooted -tree
rooted at any elementin . If is an endnode, i.e., $r\in V_{O}$ and is its unique child, we denote the rooted-tree
by. The parent-child relation $\{u, v\}$ in $E$ in a rooted -tree is denotedby $uarrow v$ which means is a parent of . Let $I_{i}(i\in A)$ be any family of closed intervals
in . Let the median two points of all the endpoints of be. Then we define the$I_{i}(i\inA)$
median interval ofby the closed interval $[x, y]$ and denote by.
For each node in the body of a rooted -tree , we assign a closed interval $I(u)$ ofrecursively as follows:$\lambda$$T$$\mathrm{e}1$

$T$

$u$

$V$

$\{\lambda(u)|\lambda\in \mathrm{R}\mathrm{m}\mathrm{p}(T)\}$

$u$

$u$

$\mathrm{R}\mathrm{m}\mathrm{p}(\tau)$$\lambda$$\lambda\in \mathrm{R}\mathrm{m}\mathrm{p}(\tau)$$S_{u}$$\mathrm{R}\mathrm{m}\mathrm{p}(\tau)$$S_{u}$$el$$\mathrm{e}1$

$V$

$r$

$r$

$T^{(r)}$$\mathrm{e}1$$T^{(r)}$$s$$(T_{s}, r)$$\mathrm{e}1$

$u$

$T$

$v$

$\Omega$$I_{i}$$\langle x, y\rangle$$\mathrm{m}\mathrm{e}\mathrm{d}\langle I_{i} :$u$$\mathrm{e}1$$I(u)=\{$$T$$[\sigma(u), \sigma(u)]$$\mathrm{m}\mathrm{e}\mathrm{d}\langle I(v) :$\Omega$

if is a leaf,
otherwise.
$u$uarrow v\rangle$

i\in A\rangle$

58This interval $I(u)$ is called the characteristic interval of a node .
From a phylogenetic point of view, Minaka $[2,3]$ has introduced the two partial orderings
to investigate the relationships among MPRs. One is the usual ordering, andon
the other is a partial ordering that depends on a state of a specified root of a given el-tree.
We now give a mathematically explicit formulation for those partial orderings. Let be
is defineded by $\lambda(u)\leq\mu(u)$ for allon
an -tree. The usual ordering
on is defined. A binary relation
be a rooted -treein . Let
ison
by $\sigma(r)\leq a\leq b$ or $\sigma(r)\geq a\geq b$ . Then, a binary relation
for all in . It is easily shown that those relations are partialdefined byis called a usual $MPR$ -poset, and theorderings. The partially-version $MPR$ -poset. Note that a usual MPR-poset isis called a-version MPR-poset, depending on a specified
uniquely defined for an -tree, but aroot, is defined in several ways for an el-tree.
We first restate some previous results which relate paticularly to new results stated later.
. We define a reconstruction on by $\lambda(u)=x$ in
Let be a rooted -tree
for any in , that is, is the least element of a subposet
satisfying. This reconstruction is well-defined since it is easily seen thatin the poset, and then this is particularly written as
the least element of each subposet. The following theorem answers for whether there exists the least element in a-version MPR-poset or not.
$u$$\mathrm{R}\mathrm{m}\mathrm{p}(T)$$T$$\lambda\leq\mu$$\mathrm{e}1$

$u$

$T$

$V$

$\mathrm{R}\mathrm{m}\mathrm{p}(T)$$a\leq_{\sigma(r)}b$$(T_{s}, r)$$\mathrm{e}1$$\Omega$$\mathrm{R}\mathrm{m}\mathrm{p}(T)$$\lambda\leq_{\sigma(r)}\mu$

$V$

$u$

$\lambda(u)\leq_{\sigma(r)\mu}(u)$$\mathrm{o}\mathrm{r}\mathrm{d}\mathrm{e}\mathrm{r}\mathrm{e}\mathrm{d}_{\mathrm{S}}\mathrm{e}\mathrm{t}(\mathrm{R}\mathrm{m}\mathrm{p}(\tau), \leq)$$\sigma(r)$$(\mathrm{R}\mathrm{m}\mathrm{p}(\tau), \leq_{\sigma(r)})$$\sigma(r)$$\mathrm{e}1$$T$$\lambda$$(T_{S}, r)$$\mathrm{e}1$$x\leq_{\sigma(r)y}$$S_{u}$$(S_{u}, \leq_{\sigma(r)})$$x$$S_{u}$$y$$T$$\lambda$$(\Omega, \leq_{\sigma(r)})$$\lambda$$(S_{u}, \leq_{\sigma(r)})$$\lambda_{\min}^{<\sigma(r)}>$$\sigma(r)$Theorem A. Letelement of

be a rooted -tree
.
$el$

$T$

$(T_{s}, r)$. Then the reconstruction$\lambda^{<\sigma(r}\min$) $>is$the least$\square$$(Rm_{P()}\tau, \leq_{\sigma(\mathrm{r})})$

dosen’t always have the greatest element. The folIt is known thatlowing shows one of the requirements for a reconstruction in Rmp $(T)$ to be a maximal. We define two-version MPR-poset. Let be a rooted -tree
element of thethe smallest element, under
on by
andreconstructions
andthe usual ordering , of maximal elements in the subposet
the greatest element, under the usual ordering , of maximal elements in the subposet$(\mathrm{R}\mathrm{m}\mathrm{p}(\tau), \leq_{\sigma(r)})$$\lambda$$T$$\sigma(r)$$\alpha^{<\sigma(r)}>$$(T_{S}, r)$$\alpha^{<\sigma(r)>}(u)=$$T$$\beta^{<\sigma(r)>}$$\mathrm{e}1$$(S_{u}, \leq_{\sigma(r)})$$\leq$$\beta^{<\sigma(r)>}(u)=$$\leq$$(S_{u}, \leq_{\sigma(r)})$.

be a rooted -tree
Proposition B. Let
maximal elements of $(Rmp(\tau), \leq_{\sigma(r)})$ .
$el$

$T$

$(T_{s}, r)$. Then, both$\alpha^{<\sigma(r)>}and$$\beta^{<\sigma(r)>}$are$\square$

The following shows a necessary and sufficient condition for ato have the greatest element.

$\sigma(r)$-version MPR-poset. $(Rmp(\tau), \leq_{\sigma(r)})$ has the greatest element
Corollary C. Let be a rooted -tree$\sigma(r)\leq\min(S_{u})$ or $\sigma(r)\geq\max(S_{u})$ .
if and only if for any in
$el$

$T$

$u$

$V_{H},$$(T_{S}, r)$$\square$Using those results, we have some new results about the characteristics of MPR-posets.
The following theorem shows the necessary and sufficient condition for an MPR to be a59

maximal element ofTheorem 1. Letof$T$$(Rmp(\tau), \leq_{\sigma(r)})\square$$(s_{u}, \leq_{\sigma()}r)$$\sigma(r)$-version MPR-poset.

be a rooted -tree
if and only if for any$el$$(T_{s}, r)$

$u$

in

and

$\lambda$$V_{H},$

in$\lambda(u)$.

$\mathrm{N}_{\mathrm{n}+_{i}}t!\mathrm{t}.\mathrm{h}\mathrm{a}.\dotplus\dotplus \mathrm{h}\mathrm{f}!\mathrm{r}\theta‘!*\mathrm{i}.\mathrm{q}+..\mathrm{q}$a.n$\partial 1_{-+.r\rho}l^{1}-T$.G llf.h-.

is a maximal element
is a maximal element of subposet$\mathrm{R}\mathrm{m}\mathrm{p}(T)$$+.\mathrm{h}\mathrm{a}.\dotplus\dotplus \mathrm{h}_{\partial}\eta 1\mathrm{l}\mathrm{m}\mathrm{h}\circ 1’\cap \mathrm{f}$$\lambda$

nll$\mathfrak{m}\mathrm{a}\mathrm{v}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{l}\iota \mathrm{o}\mathrm{l}o\mathrm{m}\mathrm{o}\mathrm{n}\star \mathrm{c}\cap \mathrm{f}$Fig. 1: A rooted -tree with $6m+3$ nodes$\mathrm{e}1$

We next show the followings which answer whether anya lattice or not.
Theorem 2. Let be a rooted -tree
forms a lower semilattice.
$T$

$el$

$(T_{S}, r)$. The$\sigma(r)$-version MPR-poset forms$\sigma(r)$-version $MPR$ -poset $(Rmp(\tau), \leq_{\sigma(r)})$$\sigma(r)$-version $MPR$ -poset $(Rmp(\tau), \leq_{\sigma(r)})$$\square$. The
Theorem 3. Let be a rooted -tree
forms an upper semilattice if and only if for anyholds.
$T$$\sigma(r)$$el$$(T_{S}, r)$

$u$

in

$V_{H},$$\sigma(r)\leq\min(S_{u})$or $\max(S_{u})\leq$$\square$

We here show some examples of the theorems stated above. Let
be an -tree
rooted at shown in Fig.2. From
shown in Table 1, we can construct a, andshown in Fig.3, whose maximal elements
version MPR-poset
for each node , and the poset forms a lower
assign a maximal element ofsemilattice.
$(T_{a},p)$$p$$(S_{u}, \leq_{\sigma(p)})$$T$$\sigma(p)-$$\mathrm{R}\mathrm{m}\mathrm{p}(T)$$(\mathrm{R}\mathrm{m}\mathrm{p}(\tau), \leq_{\sigma(p)})$$\lambda_{6}$$\mathrm{e}1$$\lambda_{1},$$u$$\lambda_{3}$60Fig. 2: a rooted -tree$\mathrm{e}1$$(T_{a},p)$We finally show the following, which is immediate from Corollary
Theorem 3.
Corollary 1. Let $T$ be a rooted
equivalent:

1. The2. The3. The-tree$el$$(T_{s}, r)$$\mathrm{C}$, Theorem 2, and. Then the following three statements are-poset has the greatest element.
-version $MPR$ -poset forms an upper-semilattice.
-version $MPR$ -poset forms a lattice.

$\sigma(r)- ver\mathit{8}i_{onMP}R$$\sigma(r)$$\sigma(r)$$\square$$\bigwedge_{7}$Table. 1:$\mathrm{R}\mathrm{m}\mathrm{p}(T)$Fig. 3:$(\mathrm{R}\mathrm{m}\mathrm{p}(\tau), \leq_{\sigma(\mathrm{p})})$

61

参考文献
[1] M. Hanazawa, H. Narushima and N. Minaka, Generating most parsimonious reconstructions on a tree:
a generalization of themethod, Discrete Applied Mathematics 56 (1995)$\mathrm{F}\mathrm{a}\mathrm{r}\mathrm{r}\mathrm{i}\mathrm{s}-\mathrm{S}_{\mathrm{W}}\mathrm{o}\mathrm{f}\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{d}- \mathrm{M}\mathrm{a}\mathrm{d}\mathrm{d}\mathrm{i}_{\mathrm{S}\mathrm{o}\mathrm{n}}$245-265.

[2] N. Minaka, Parsimony, phylogeny and discrete mathematics: combinatorial problems in phylogenetic systematics (in Japanese: with English summary), Natural History Research, Chiba Prefectural
Museum and Institute, Vol.2 No.2 (1993) 83-98.

[3] N. Minaka, Algebraic Properties of the Most Parsimonious Reconstructions of the Hypothetical Ancestors on a Given, Forma 8 (1993) 277-296.
$\mathrm{b}\mathrm{e}\mathrm{e}$$\mathrm{L}\mathrm{r}4]$

H. Narushima and M. Hanazawa, A more efficient algorithm for MPR problems in phylogeny, Discrete
Applied Mathematics 802-3 (1997) 227-234.

[5] H. Narushima and N. Misheva, On a role of the MPR-poset of most-parsimonious reconstructions inphylogenetic analysis–A combinatorial optimization problem in phylogeny-, in: W. Y. C. Chen,
D. Z. Du, D. F. Hsu, H. Y. Hap (Eds.), Proc. The International Symposium on Combinatoircs andApplications 28-30, June, 1996, Tianjin, P.R.China, pp. 306-313.
[6] H. Narushima and N. Misheva, On characteristics of ancestral
the accelerated transformation optimization, preprint.

-state reconstructions under$\mathrm{C}\mathrm{h}\mathrm{a}\mathrm{r}\mathrm{a}\mathrm{C}^{*}.\mathrm{e}\mathrm{r}$[7] H. Narushima, On extremal properties of ACCTRAN reconstructions in phylogeny, preprint.

[8] 成嶋弘, 系統樹最節約復元問題の大域的最適解について (On globally optimal reconstructions of phylogenetic trees), 京大数解研講究録 992 『計算理論とその応用 Jl (1997 年 5 月), 5-11.
[9] 成嶋弘, 祖先形質の最節約復元順序集合について (On MPR-posets in phylogeny), 京大数解研講究録
1041 j アルゴリズムと計算の理論』 (1998 年 4 月), 44-49.

[10] 宮川幹平, 成嶋弘, 最節約復元順序集合の極値問題について (On extremal problems of MPR-posets),
京大数解研講究録 10410 アルゴリズムと計算の理論 Jl (1998 年 4 月), 50-55.