Biology Reference
In-Depth Information
formulation, the rationale for the
Q
-criterion is nonobvious. The next exercise helps
shed some light on the cherry-picking criterion, when
|
X
|=
4.
Exercise 10.17.
For the quartet
T
=
((A,B),(C,D));
as in Example
10.3
,
there are five edges
(
u
,
A
), (
u
,
B
), (
u
, v), (v,
C
), (v,
D
)
. No matter what values an
edge-weighting
actually assigns to these five edges, if we use the tree metric
D
T
,ω
in place of
c
in the cherry-picking criteria, then, using the first expression for
Q
in
Theorem
10.2
, the summands in the expression for the
Q
-values are basically just sums
of path lengths along
T
. For example, the first term in
Q
ω
(
A
,
B
)
is
(
4
−
2
)(ω(
u
,
A
)
+
ω(
, or twice the length of the path from
A
to
B
. The next summand subtracted
off is the sum of three terms: the length of the path from
A
to
B
, the length of the path
from
A
to
C
, and the length of the path from
A
to
D
. The last summand subtracted off
is the sum of three terms just like the last, but starting from
B
and going to
A
,to
C
,
and then to
D
. Thus the path lengths from
A
to
B
cancel out completely, and in what
remains, each length from a leaf to its parent node (i.e.,
u
,
B
))
(ω(
A
,
u
), ω(
B
,
u
), ω(
C
,v)
,
and
ω(
D
,v)
) appears twice, while the length
ω(
u
,v)
from
u
to
v
appears four times,
and all are then multiplied by
−
1togive
Q
(
A
,
B
)
=−
2
(ω(
A
,
u
)
+
ω(
B
,
u
)
+
ω(
. (By tracing over the graph, one can even just
graphically represent all the path pieces described above and visually see the cancel-
lations/reduction to this expression for
Q
C
,v)
+
ω(
D
,v))
−
4
(ω(
u
,v))
(
,
)
A
B
.) To complete this exercise:
1.
Do a similar analysis for
Q
(
A
,
C
)
and explain why
Q
(
A
,
C
)>
Q
(
A
,
B
)
.
2.
Explain why likewise
Q
.
3.
Observe by symmetric arguments that only two possible things can happen:
Q
(
A
,
D
)>
Q
(
A
,
B
)
(
A
,
B
)<
Q
(
i
,
j
)
for all other pairs
{
i
,
j
}
in
X
OR
Q
(
A
,
B
)
=
Q
(
C
,
D
)
, and
otherwise both are less than
Q
(
i
,
j
)
when
{
i
,
j
} ={
A
,
B
}
or
{
C
,
D
}
.
Exercise
10.17
shows that the cherry-picking criteria at least makes sense for
unrooted binary quartet trees, since there is only one topology to consider. There is a
much stronger connection between quartets and the NJ Algorithm, as is given by the
next theorem, shown, e.g., in [
25
].
Theorem 10.3.
|
|=
4
and D is a dissimilarity map on X, then the NJ Algorithm
returns a tree that satisfies the four-point condition.
As suggested by the last part of Exercise
10.17
, in general, while the NJ Algorithm
will pick out the pair of cherries with minimal distance between them first, if there are
two or more pairs of cherries with the same distance between them, any of thesemay be
chosen first. Thus, more generally, the order of choosing cherries in the NJ Algorithm
may not be unique (i.e., when multiple pairs of leaves have the same
Q
-values).
If the NJ Algorithm selects taxa
If
X
{
k
,
l
}
as a cherry, and
a
k
,
l
is the new node joining
n
−
1
2
, then the new dissimilarity map
c
∈
R
{
k
,
l
}
is defined to be
c
i
,
j
if
i
=
a
k
,
l
=
j
=
c
i
,
j
2
c
i
,
k
+
c
k
,
l
.
1
c
i
,
a
k
,
l
else
=
c
i
,
l
−
Search WWH ::
Custom Search