Biology Reference
In-Depth Information
1
2
3
4
5
v
v
v
v
v
(1, 1, 1)
1
w
g
1
23456
(0, 0, 2)
ggggg
(1, −1, 1)
(−1, −1, 1)
2
w
(−1, 1, 1)
(0, −2, 0)
(1, −1, −1)
Fig. 6.3. The consecutive genotypes of a
path in (
H,G,E
) are indicated with an arc.
So, there is path that contains the sequence
g
2
,h
,g
4
,h
,g
5
, but there is no path that
contains
g
1
,h,g
3
.
Fig. 6.2. In this example
η
(
{v
1
,v
3
,v
5
}
=
V
2
and
φ
(2) = 3.
G
for
which all elements are comparable forms a chain of genotypes. For example, the
following four genotypes form a chain,
n
is a poset under componentwise comparisons of
{−
2
,
0
,
2
}
. A subset of
(
−
2
,
2
,
0
,
2
,
−
2)
(0
,
2
,
0
,
0
,
−
2)
(0
,
2
,
0
,
0
,
0)
(0
,
0
,
0
,
0
,
0)
.
Chains have the property that as we look up the chain from smaller to greater
elements that once a 2 or
2 becomes a 0 it remains 0. The following lemma and
theorem solve the pure parsimony problem in the special case that
−
G
is a chain.
G
Lemma 6.4.
For the diversity graph
(
V
,
W
,
E
,η,γ
)
assume that
γ
(
W
)=
V
)
be a minimal solution and assume that
g
∈G
forms a chain under
.Let
η
(
. Then there does not exist
v
and
has the property that
γ
(
w
)
≺
g
, for all
w
∈W
v
in
V
such that
η
(
v
)+
η
(
v
)=
g
.
|G
|
V
=
v
,v
}
and the result follows because
η
(
v
)+
Proof.
If
=1,then
{
η
(
v
)
∈G
but
g
∈G
.
|G
|≥
So, assume that
2.
Suppose for the sake of
attaining a contradiction that there is a
v
and
v
in
V
such that
η
(
v
)+
η
(
v
)=
g
.
V
) is a minimal solution to
G
, there are no isolated nodes in
V
.Since
Because
η
(
g
∈G
, this implies that there exists
v
and
v
in
V
such that
η
(
v
)+
η
(
v
) and
η
(
v
)+
η
(
v
) are distinct elements of
G
. Without loss of generality, we assume
that
η
(
v
)+
η
(
v
)
η
(
v
)+
η
(
v
).
Since
η
(
v
)+
η
(
v
)
≺
≺
g
and
g
=
η
(
v
)+
η
(
v
), we have from the definition
of
⊕
that
η
(
v
)
η
(
v
)
η
(
v
)=
η
(
v
)
η
(
v
)
.
⊕
⊕
⊕
Similarly, because
η
(
v
)+
η
(
v
)
<η
(
v
)+
η
(
v
) and
η
(
v
)
η
(
v
)
η
(
v
)
η
(
v
)=
η
(
v
)
η
(
v
)
,
⊕
⊕
⊕
⊕
Search WWH ::
Custom Search