Biology Reference
In-Depth Information
graphic
, meaning that (
h
1
,
h
2
,...,
h
n
)
<
(
h
1
,
h
2
,...,
h
n
) if the first compo-
nent with different values satisfies
h
i
<
h
i
. The proof of this lemma is simple
and omitted.
Lemma 6.1.
If the elements of
are ordered lexicographically, then for unique
i
and
j
between
1
and
2
n
we have that
h
i
+
h
i
+1
H
=
h
j
+
h
j
+1
and that
h
j
+
h
(2
n
−j
+1)
=(0
,
0
,...,
0)
.
Since haplotypes mate in unique pairs to form a genotype, the degree of every
node in
is even. An immediate consequence of this observation is that not ev-
ery bipartite graph supports diversity. Moreover, even if every node of a bipartite
graph has even degree it does not mean the graph supports diversity. As an exam-
ple, the complete bipartite graph
K
2
,
2
does not support diversity because any
η
and
γ
that satisfies the third and fourth conditions of the definition violates the fact
that
γ
is one-to-one. Theorem 6.1 does not characterize the graphs that support
diversity, but it does establish a necessary condition.
V
,η,γ
)
be a diversity graph. Let
w
1
and
w
2
be in
Theorem 6.1.
Let
(
V
,
W
,
E
W
,
with
w
1
=
w
2
. Then,
deg(
w
1
)
,
deg(
w
2
)
N
(
w
1
)
N
(
w
2
)
max
{
}≥
2
|
∩
|
.
H
=
{η
(
v
):
v ∈ N
(
w
1
)
∩N
(
w
2
)
}
Proof.
Let
and assume to the contrary that
deg(
w
1
)
,
deg(
w
2
)
|H
|
max
{
}
<
2
.
Since haplotypes mate in unique pairs, there must be fewer than
|H
|
pairs of
haplotypes mating to form each of
γ
(
w
1
)=
g
1
and
γ
(
w
2
)=
g
2
. It follows that
1
,
h
2
,
h
3
and
h
4
in
H
1
+
h
2
=
g
1
and
h
3
+
h
4
=
g
2
.
there exists
h
such that
h
1
j
=2, which means
h
j
=1for all
h
∈H
. It follows that
g
2
Suppose that
g
j
=2.
1
2
1
2
Similarly, if
g
j
=
−
2,wehavethat
g
j
=
−
2. Suppose that
g
j
=0.Then
g
j
can
1
not be 2 or
−
2 because if so, the same argument would guarantee that
g
j
is 2 or
2
−
2, respectively. We conclude that
g
j
=0.Since
j
was arbitrary, we have the
1
=
g
2
.
contradiction that
g
We now turn our direction to a matrix equation that is satisfied by every di-
versity graph. Consider the diversity graph (
V
,
W
,
E
,η,γ
),where
|V|
=
m
and
|W|
=
k
. List the elements of
V
as
v
1
,v
2
,...,v
m
and
W
as
w
1
,w
2
,...,w
k
,
and assume that
η
(
v
i
)=
h
i
and
γ
(
w
i
)=
g
i
.Let
H
be the
m
n
matrix so that
H
(
i,j
)
=
h
i
j
,andlet
G
be the
k ×n
matrix defined by
G
(
i,j
)
=
g
i
j
.Alsolet
E
be
the
m
×
k
biadjacency matrix —i.e.
E
(
i,j
)
=1if (
v
i
,w
j
)
and
E
(
i,j
)
=0
otherwise. Note that the column sums of
E
must be even from the definition of a
diversity graph.
×
∈E
Search WWH ::
Custom Search