Biology Reference
In-Depth Information
The best bound provided by Corollary 6.1 is the one that minimizes q .Anin-
teresting question for future research is whether or not calculating the minimum
value of q actually solves the pure parsimony problem in some cases.
Instead of addressing the smallest size of a solution to a chain, the next result
and its corollary considers how large a minimal solution can be.
Theorem 6.10. Let (
V
,
W
,
E
,η,γ ) be a diversity graph such that η (
V
)=
H
,
E
G is a chain with respect to
is as large as possible, and γ (
W
)=
. Assume that
the elements of
W
are ordered so that
γ ( w |G | ) .
γ ( w 1 )
γ ( w 2 )
...
Assuming that γ ( w 2 ) has 3 or more zero SNPs, we have that there is a minimal
solution to
G with cardinality 2
|G |
.
|G |
|G |
Proof.
The proof is by induction on
. The result clearly holds if
=1,
|G |≤
|G |
andweassumetheresultistruefor
k . Assume that
= k +1,andlet
V ) be a minimal solution to
G =
G \{
γ ( w k +1 )
|G |
η (
}
whose cardinality is 2
.
V
such that η ( v )+ η ( v )= γ ( w k +1 ). We show that there is a minimal solution
η (
V ) does not solve
G
because there is no v
and v
From Lemma 6.4, η (
in
V ) such that
V ⊆V
|V |
|V |
.
Because γ ( w k +1 ) is the k +1 element in a chain, it has at least k +1 ambiguous
SNPs, and thus
and
+2=
N ( w k +1 )
2 k +1 . Since we assumed that γ ( w 2 ) has at least 3
|
|≥
N ( w k +1 )
> 2 k +1 .For j
2 j , and thus 2 k<
zero SNPs,
|
|
1,wehave2 j
N ( w k +1 )
N ( w k +1 )
/ 2 is the number of adjacent pairs to w k +1 and
|
|
/ 2.Since
|
|
|V |
=2 k ,thereisa v and v in N ( w k +1 )
V ) such that η ( v )+ η ( v )=
\
N (
γ ( w k +1 ). Thismeansthat η (
V ∪{
v ,v }
G whose
) is a minimal solution to
|G |
cardinality is 2
.
The condition of γ ( w 2 ) having at least 3 zero SNPs is not imposed because this
proof requires it, but rather, it is needed by any proof due to the following example.
Let
G =
{
(
2 , 0) , (0 , 0)
}
. Then a four element solution would have the form
{
1 and y is the other.
In either case an element is duplicated, and hence there is no solution of size 4.
The following corollary establishes that under the conditions of Theorem 6.10,
there is a minimal solution of every cardinality between the minimum value of
|G |
(
1 , 1) , (
1 ,
1) , ( x, 1) , ( y,
1)
}
,where x is either 1 or
|G |
+1and the maximum value of 2
.
G ,
Corollary 6.2. Let (
,η,γ ) be a diversity graph satisfying the condition of
Theorem 6.10. Then, there is a minimal solution of cardinality j for
V
,
E
|G |
+1
|G |
j
2
.
Search WWH ::




Custom Search