Biology Reference
In-Depth Information
complex if
m>
1, and one of the main goals of this section is to show that
φ
(2)
can be calculated by decomposing an acyclic diversity graph into longest paths.
1
2
3
4
5
6
v
v
v
1
w
2
w
w
w
v
3
v
4
v
v
v
v
5
w
7
8
9
6
w
V
1
=
∅
,
φ
(1) =
∞
V
2
=
V
,
φ
(2) = 9,and
m
∗
=2.
Fig. 6.1.
A graph for which
,
V
m
.For
instance, if a haplotype is not compatible with more than
m
genotypes, then allow-
ing it to mate with
m
+1haplotypes provides no additional benefit. Hence, for
some
m
,
φ
(
m
)=
φ
(
m
+
k
) for every natural number
k
. Moreover, increas-
ing the number of possible mates that any haplotype is allowed never causes
an increase in
φ
(
m
), and hence,
φ
is non-increasing. The smallest
m
such that
φ
(
m
)=
φ
(
m
+
k
),forall
k
At some threshold, increasing
m
does not change the cardinality of
, is denoted by
m
∗
. Clearly we have that
∈
N
m
∗
≤
max
{
deg(
v
):
v
∈V}≤|W|
.
An important observation is that
φ
(
m
∗
) is the solution to the pure parsimony
problem. So, if we knew how
φ
grew as
m
increased and how to bound
m
∗
,
then we could estimate the size of a biologically relevant collection of haplotypes.
Unfortunately, we do not know the answer to either of these questions at this
point, but these and related questions have future research promise. We initiate
the investigation by studying
φ
(2) and
φ
(
) if
m
∗
=
|W|
|W|
, the latter of which is
addressed below.
Theorem 6.7.
If
m
∗
=
,then
φ
(
m
∗
)=
|W|
|W|
+1
.
Let
m
∗
=
. Then, there exists
v
∈V
m
such that for each
w
i
Proof.
|W|
∈W
there is a unique
v
i
∈V
m
\{
v
}
that satisfies
η
(
v
)+
η
(
v
i
)=
η
(
w
i
). This means
Search WWH ::
Custom Search