Biology Reference
In-Depth Information
|H
∗
|
|G
|
if and only if
N
(
w
)
N
(
w
)=
Theorem 6.6.
We have that
=2
∪
∅
for
all
w
and
w
in
W
.
|H
∗
|
|G
|
if
N
(
w
)
N
(
w
)=
for all
w
and
w
Proof.
The fact that
=2
∪
∅
|H
∗
|
|G
|
in
W
is clear. Assume that
=2
, and suppose for the sake of obtaining
a contradiction that
T
(
w
)
=
∅
for some
w
∈W
.
From Lemma 6.3 we have
H
∗
contains an element in
w∈W
η
(
T
(
w
)).Let
w
1
and
w
2
be such that
η
(
v
1
)+
η
(
v
2
)=
γ
(
w
1
) and
η
(
v
1
)+
η
(
v
3
)=
γ
(
w
2
),forsome
v
1
,
v
2
,and
v
3
.Let
W
=
that
w
1
,w
2
V
=
V
)
∗
be such
W\{
}
,andlet
∪
w∈W
N
(
w
). Furthermore, let (
V
)
∗
) is a minimum solution to
γ
(
W
) with respect to (
V
,
W
,
E
),where
that
η
((
E
is
E
with the edges incident to
w
1
and
w
2
removed. Then,
|
η
((
V
)
∗
)
|≤
|G
|
2
.
G
by including
v
1
,
v
2
,and
v
3
in (
H
)
∗
. Since all
three haplotypes might not be required, we have that 2
We know that we can resolve
|G
|
=
|H
∗
|≤|
(
H
)
∗
|
+3.
So,
|G
|
|H
∗
|≤|
V
)
∗
|
|W
|
|G
|−
2
=
(
+3
≤
2
+3=2(
|W|−
2) + 3 = 2
1.
Since this is a contradiction, we have that
T
(
w
)=
∅
for all
w
, and consequently,
N
(
w
)
N
(
w
)=
,forall
w
=
w
.
∩
∅
We continue our investigation by exploring the effects of restricting the num-
ber of times a haplotype can be used to form a genotype. This makes sense realis-
tically since in many populations the mating structure is not random. For example,
many species have a unique mate for life, which means their haplotypes are only
used in conjunction with the haplotypes of another individual. To make this pre-
cise, we reduce the edge set of the initial graph. For any
E
⊆E
we define the
E
to be deg
E
(
v
)=
∈E
}|
degree of
v
with respect to
|{
(
v,w
):(
v,w
)
.Forthe
V
m
⊆V
diversity graph (
V
,
W
,
E
,η,γ
) we let
be any solution to
{|V
|
V
⊆V
V
) solves
γ
(
min
:
,η
(
W
)
,
∈V
}
E
⊆E}
max
{
deg
E
(
v
)
≤
m
:
v
for some
.
(6.6)
|V
m
|
The value of this optimization problem is denoted
φ
(
m
)=
, and if the prob-
lem is infeasible, we let
φ
(
m
)=
∞
. As an example, consider the graph in Fig. 6.1,
which is easily seen to support diversity. Since deg(
w
i
)=2for all
i
except 3,the
only solution is
η
(
{
v
i
:
i
=1
,
2
,...,
9
}
).If
m
=1, then each
v
can be adjacent
E
. This means we must be able to associate a
to at most one
w
with respect to
unique pair in
. Biologically this means that each parent
can donate one of its two haplotypes to a unique child. Since this is impossible for
this graph, we have that
φ
(1) =
V
with each element of
W
∞
. Notice that in general we have
φ
(1) is either
2
|W|
or
∞
depending on whether or not (6.6) is feasible. The situation is more
Search WWH ::
Custom Search