Biology Reference
In-Depth Information
FIGURE 10.4
Edge-weighted quartet tree
T
on
X
={
a; b; c; d
}
;
for Example 10.5
Exercise 10.12.
a.
For the tree
T
and edge-weighting
ω
as in Example
10.5
, for each set of three ele-
,
,
∈
X
, calculate
d
T
,ω
(
,
)
+
d
T
,ω
(
,
)
and compare it to
d
T
,ω
(
,
)
ments
i
j
k
i
k
k
j
i
j
.
For example, for
i
=
a
,
j
=
b
, and
k
=
d
,
d
T
,ω
(
i
,
k
)
+
d
T
,ω
(
k
,
j
)
=
2
.
5
+
2
3. How do these compare? What happens for the
other combinations, including when two or more of
i
.
5
=
5, while
d
T
,ω
(
i
,
j
)
=
,
j
,
k
are equal? Interpret
your observations graphically.
b.
Starting again with the notation of Example
10.5
, for the fixed choices
i
=
a
,
j
=
b
,
k
=
c
,
l
=
d
, calculate the quantities
d
T
,ω
(
i
,
j
)
+
d
T
,ω
(
k
,
l
),
d
T
,ω
(
i
,
k
)
+
d
T
,ω
(
. What do you notice? Does your conclusion
change if you take other choices of
i
j
,
l
),
d
T
,ω
(
i
,
l
)
+
d
T
,ω
(
j
,
k
)
X
?
c.
For any quartet tree (that is, any unrooted tree with four leaves) for which
i
and
j
are sisters (cherries, here), use a graphical interpretation of relevant paths along
the tree to argue that
,
j
,
k
,
l
∈
d
T
,ω
(
i
,
j
)
+
d
T
,ω
(
k
,
l
)<
d
T
,ω
(
i
,
k
)
+
d
T
,ω
(
j
,
l
),
and
d
T
,ω
(
i
,
k
)
+
d
T
,ω
(
j
,
l
)
=
d
T
,ω
(
i
,
l
)
+
d
T
,ω
(
j
,
k
),
for any positive edge-weighting
ω
on
T
.
The
four-point condition
for a dissimilarity map
D
on a set
X
is satisfied if
d
(
u
,v)
+
d
(
x
,
y
)
max
{
d
(
u
,
x
)
+
d
(v,
y
),
d
(
u
,
y
)
+
d
(v,
x
)
}
,
for any
u
X
, where by definition the right-hand side of the inequality is the
largest (“max”) of the two sums indicated.
Exercise 10.13.
,v,
x
,
y
∈
1.
Show that any quartet tree satisfies the four-point condition.
Search WWH ::
Custom Search