Biology Reference
In-Depth Information
Let
ˆ
V
I
be a set of nodes of size (2
M
W
−
M
V
)
+
+
M
V
(mod2) , which guaran-
ˆ
tees that
|V
I
∪
V
I
|
is even and at least twice the size of
W
I
. List the elements
ˆ
W
I
as
w
1
,w
2
,...,w
M
W
and the elements in
V
I
as
v
1
,v
2
,...,v
q
,where
in
V
I
∪
M
V
)
+
+
M
V
(mod2) .For
i
=1
,
2
,...,M
W
,add(
v
2
i−
1
,w
i
)
q
=
M
V
+(2
M
W
−
and (
v
2
i
,w
i
) to
¯
E
. Notice that this may leave some isolated nodes in
V
I
,which
2
k
1
,
h
2
,...,
h
is allowed by the definition. Let
h
be a lexicographic ordering of
k
.Define
η
:
¯
ˆ
n
+
k
by
V
∪V
I
∪
{−
1
,
1
}
V
I
→{−
1
,
1
}
¯
(
η
(
v
)
,
1
,
1
,...,
1)
,
V
v
∈
i
+1
)
,
v
=
v
i
,i
=1
,
2
,...,q/
2
(1
,
1
,...,
1
,
h
v
→
2
k
−i
+(
q/
2)
)
,v
=
v
i
,i
=
q/
2+1
,q/
2+2
,...,q
(1
,
1
,...,
1
,
h
n
+
k
so that
and
γ
:
W→{−
2
,
0
,
2
}
(
γ
,
2
,
2
,...,
2)
,
∈W
(2
,
2
,...,
2
,η
(
v
2
i−
1
)+
η
(
v
2
i
))
,w
=
w
i
,i
=1
,
2
,...,M
W
∈W
I
,
where the uniqueness of
η
(
v
2
i−
1
)+
η
(
v
2
i
) follows from Lemma 6.1.
w
w
→
6.4. Algorithms and Solutions for the Pure Parsimony Problem
Although the pure parsimony is generally difficult, there are cases where a closed
form solution exists. Throughout this section we assume that (
V
,
W
,
E
,η,γ
) is a
G
. We also assume that
diversity graph with the property that
γ
maps
W
onto
H
∗
⊆
,η,γ
).
We begin by establishing the intuitive result that a minimal solution has car-
dinality 2
η
(
V
) is a minimal solution relative to (
V
,
W
,
E
|G
|
are disjoint.
Although this fact is nearly obvious, we include a proof for completeness. The
following lemma supports the result.
if and only if the neighborhoods of the elements in
W
H
∗
contains an
Lemma 6.3.
Suppose that
T
(
w
)
=
∅
for some
w
∈W
. Then,
element of
w∈W
η
(
T
(
w
))
.
H
∗
does not
Proof.
Assume that
T
(
w
)
=
∅
for some
w
∈W
and suppose that
contain an element of
w∈W
η
(
T
(
w
)). Then for each
w
there is a
v
and
v
in
\
w∈W
η
(
T
(
w
)) so that
η
(
v
)+
η
(
v
)=
γ
(
w
). Thisimpliesthat
|H
∗
|
N
(
w
)
=
|G
|
2
. However, we know that
T
(
w
) is nonempty for some
w
, which means there
exists
w
1
and
w
2
such that
η
(
v
1
)+
η
(
v
2
)=
γ
(
w
1
) and
η
(
v
1
)+
η
(
v
3
)=
γ
(
w
2
)
for some
v
1
,
v
2
,and
v
3
in
V
.Thismeansthat
H
∗
\{
∅}
∪{
∈H
∗
,
(
v,w
1
)
,
(
v,w
2
)
η
(
v
1
)
,η
(
v
2
)
,η
(
v
3
)
η
(
v
):
η
(
v
)
{
}∩E
}
=
G
whose cardinality is at most
|H
∗
|−
is a solution to
1, which is a contradiction.
Search WWH ::
Custom Search