Biology Reference
In-Depth Information
a labeled (or colored) bipartite graph with one set of nodes representing geno-
types, the other set representing haplotypes, and edges representing the possible
relationships between them.
H
⊂H
G
⊂G
Definition 6.1.
For
and
, a bipartite graph (
V
,
W
,
E
), and func-
V→H
and
γ
:
W→G
,wesay(
tions
η
:
V
,
W
,
E
,η,γ
) is a
diversity graph
on
n
SNPs if
(1)
η
and
γ
are one-to-one,
(2) for each
w
∈W
, there exists some
v
∈V
such that (
v,w
)
∈E
,and
has the property that if (
v
,w
)
, there exists some
v
∈V\{
v
}
(3)
E
∈E
such that (
v
,w
)
and
h
+
h
=
g
,where
h
=
η
(
v
),
h
=
η
(
v
),
∈E
and
g
=
γ
(
w
).
The requirement that
η
and
γ
be one-to-one ensures that each haplotype and geno-
type are represented by exactly one node. The rest of the definition guarantees that
H
is a solution to
G
.If
η
(
v
)+
η
(
v
)=
γ
(
w
), we say that
v
and
v
or
η
(
v
) and
η
(
v
) are
mates
for
w
or
γ
(
w
). Notice that a diversity graph is a labeled bipartite
graph, and we make the distinction between the structure represented by the graph
and the biology represented by the labeling. The elements of
H
and
G
are denoted
by
h
and
g
or by
η
(
v
) and
γ
(
w
),where
v
and
w
are elements of
V
and
W
.Dif-
ferent elements of
are indicated with superscripts and SNP locations are
indicated with subscripts. We say that a bipartite graph
supports diversity
if there
are sets
H
and
G
H
⊆H
G
⊆G
, and functions
η
and
γ
that fulfill the definition.
An important observation is that the pure parsimony problem as stated as-
sumes that
and
G
is as large as possible. How-
ever, the parsimony problem makes sense on other graphs, and in general we
address the problem of starting with a diversity graph (
is known, that
η
(
V
)=
H
and that
E
V
,
W
,
E
,η,γ
) and finding
V
, such that
a smallest subset of
V
,say
V
) is a solution to
γ
(
G
,and
•
η
(
W
)=
if
v
V
, then they are allowed to mate and form
w
if and
only if (
v
,w
) and (
v
,w
) are in
and
v
•
are in
E
.
H
So, when we say that
is a minimal or minimum solution we mean that it is a
solution with respect to a diversity graph. If
V
and
η
are such that
η
(
V
)=
H
and
E
is as large as possible, then we are considering the original parsimony problem.
Before continuing with an investigation into the bipartite graphs that support
diversity, we establish some general results about diversity graphs. The first of
these results shows how to order the elements of
H
so that we can conveniently
pair them to form the genotype (0
,
0
,...,
0).
The imposed ordering is
lexico-
Search WWH ::
Custom Search