Biology Reference
In-Depth Information
(1
/
2)deg(
w
j
). Let every element of the first column of each
E
k
be a zero except for the
k
1
and
k
1
positions, which are both set to 1.Ifthe
deg(
w
1
)=deg
w
2
), form the second column of each
E
k
similarly, replacing
1
and 1
with 2
and 2
.Otherwise,deg(
w
1
)
>
deg(
w
2
) and this construction
terminates once
k
reaches (1
/
2)deg(
w
2
). In this case, let the second column of
E
k
,for(1
/
2)deg(
w
2
)+1
where 1
≤
k
≤
s
, be the same as the second column of
E
1
.
Continue in this fashion through the remaining nodes in
≤
k
≤
, duplicating columns
from
E
1
as needed. From (6.2) we have that
E
(
i,j
)
=1if and only if
E
(
i,j
)
=1
for at least one
k
, from which we conclude that
E
=
E
1
W
E
s
.
Let
H
and
G
be the matrices in Theorem 6.2. Each column of
E
k
corresponds
to an element of
E
2
∨
∨
...
∨
that in turn corresponds to a genotype under
γ
. Moreover,
each column of
E
k
contains two 1s that identify a pair of haplotypes (via
η
)that
mate to form the genotype. So, each column sum of every
E
k
sums to 2 and
(
E
k
)
T
H
=
G
,forevery
k
. From the fact that
γ
is one-to-one we have that the
rows of (
E
k
)
T
H
are distinct.
Now assume that
E
has a logical decomposition, say
E
1
,E
2
,...E
s
,thatsat-
isfies the three conditions. List the elements of
W
and define
η
(
v
i
)
to be the
i
th
row of
H
. The fact that the rows of
H
are unique ensures that
η
is one-to-one. Similarly, list the nodes in
V
from 1 to
|V|
and let
γ
(
w
i
) be the
W
from 1 to
|W|
i
th
row of (
E
k
)
T
H
, which is common for 1
s
. The assumption that the
rows of (
E
k
)
T
H
are distinct guarantees that
γ
is one-to-one. From the condition
that each column sum of
E
k
is 2, we have that each column of
E
hasatleasttwo
ones. This means that there are at least two elements of
V
that are adjacent to
each element of
W
. The same condition together with the definition of
η
and
γ
further guarantee that if (
v
,w
)
≤
k
≤
, then there is a
v
so that (
v
,w
)
∈E
∈E
and
η
(
v
)+
η
(
v
)=
γ
(
w
).
The logical decomposition in Theorem 6.4 extends Theorem 6.2 to characterize
graphs that support diversity by adding the necessary condition that the edge struc-
ture must accommodate a mating structure. The fact that (
E
1
)
T
H
=(
E
2
)
T
H
=
...
=(
E
s
)
T
H
shows that every pairwise differences (
E
i
)
T
(
E
j
)
T
must share
a non-trivial null space, which is restrictive and demonstrates that bipartite graphs
that support diversity are rare.
The last two results indicate that the structural requirements needed to support
diversity are important and that most bipartite graphs can not be labeled to rep-
resent a population. We point out that this is true even with the number of SNPs
being arbitrary, which is somewhat counter intuitive because the complexity of a
mating scheme can increase as the number of SNPs grows. We conclude this sec-
tion by showing that we can add nodes and edges to any bipartite graph so that it
−
Search WWH ::
Custom Search