Biology Reference
In-Depth Information
≤|G |
Proof.
For 1
i
,let
γ ( w 1 ) ( w 2 ) ,...,γ ( w |G |−i +1 )
G 1 =
{
}
and
γ ( w |G |−i +2 ) ( w |G |−i +3 ) ,...,γ ( w |G | )
G 2 =
{
}
G . By Theorem 6.9 there is a solution η (
G 1 of cardinality
be subchains of
V 1 ) to
|G |−
G 2 of cardinality
i +2and by Theorem 6.10 there is a solution η (
V 2 ) to
G 1 =
G
G 2 =
2 i
. In this case Theorem 6.9
establishes that we can indeed find a solution of cardinality
2.If i =1, notice that
and that
|G |
+1. For other
values of i we have that if
V 1 and
V 2 are disjoint, then
V 1 ∪V 2 is a minimal
|G |
≤|G |
solution whose cardinality is
+ i ,for1
i
.So,allthatislefttoshow
is that
V 2 may be selected so that they are disjoint. We accomplish this by
showing that as i increases to i +1that there are always enough elements of
V 1 and
V
to
allow
V 2 to be disjoint.
For i =1 , 2 ,...,
V 1 and
2 |G |−i +2 . As in the proof
|G |
|G |−
we have that
i +2
of Theorem 6.10, we have that
2 |G |−i +2 <
N ( w |G |−i +2 )
/ 2 ,
which guarantees that there are v and v in N ( w |G |−i +2 )
|
|
\
η (
V 1 ) such that
η ( v )+ η ( v )= γ ( w |G |−i +2 ).So,as i increases from i to
|G |
, we are guar-
anteed to be able to select disjoint
V 1 and
V 2 .
6.5. Directions for Future Research
The goal of this paper was to establish an initial investigation into the structure of
haplotyping problems by studying the underlying graph theory. We have shown
that the structural requirements of the problem are meaningful and that the ma-
jority of bipartite graphs are incapable of representing the underlying biology We
have further established a solution to the pure parsimony problem in a few cases,
and in particular we have shown that ordering the genotypes with
and decom-
G into chains bounds the problem. During the writing of this paper the
authors had other questions that were left unanswered, many of which promise to
be fruitful continued research:
posing
Although the matrix equation and the logical decomposition stated in
Theorem 6.4 characterize the graphs that support diversity, we would
have enjoyed a more graph theoretical characterization. A theorem like
(
) supports diversity if and only if it does not contain a certain
structure would have been particularly appealing.
V
,
W
,
E
Search WWH ::




Custom Search