Biology Reference
In-Depth Information
Recall our geometric perspective that, for a given a fixed
n
=|
X
|
, and a dissimi-
larity map (distance matrix)
D
,to“fit”atreeto
D
is to find a pair
T
so that
D
T
,ω
and
D
are “close.” The NJ method is at least consistent: If a tree metric
D
T
,ω
,ω
is given
as the input
D
, then
D
T
,ω
will be returned as the output.
3) and
D
=
λ
Exercise 10.19.
Suppose
D
is an
n
×
n
dissimilarity map (
n
D
,
, that is,
d
(
for some positive constant
λ
i
,
j
)
=
λ
d
(
i
,
j
)
for all 1
i
,
j
n
.
1.
Explain why, in the first iteration of the
Q
-criterion for
D
and
D
, there will be
the same choices of cherries to pick, i.e., if
{
i
,
j
}
is a cherry for
D
then it is also
one for
D
, and vice versa.
2.
Continuing, suppose that if there is more than one choice of cherry to pick, then
one picks the same cherry for both
D
and
D
. Now explain why the distance from
the new node joining this cherry for
D
is
λ
times that for
D
.
3.
If one always continues to pick the same cherries (whenever a choice is offered),
explain why the trees returned by applying the NJ Algorithm to
D
and to
D
will
have the same underlying leaf-labeled tree topology.
The NJ Algorithm constructs a weighted (binary) phylogenetic
X
-tree
T
,ω
from
a dissimilarity map
D
on
X
. As a tree,
T
has vertices
V
, with
X
V
, and the
NJ Algorithm proceeds by constructing the set
V
, edges
E
, and edge-weights
⊂
ω
from the data
D
on
X
.An
order
σ
of picking cherries
in the NJ Algorithm when
outputting the pair
T
,ω
from
D
could be defined as a sequence of pairs
σ
=
(
{
i
1
,
j
1
}
,
{
i
2
,
j
2
}
,
{
i
3
,
j
3
}
,...,
{
i
r
,
j
r
}
)
of elements
i
a
,
j
b
∈
V
,forwhich
{
i
k
,
j
k
}
is
the
kth
cherry to be picked. The first cherry
{
i
1
,
j
1
}
is a subset of
X
, but the remaining
pairs may involve interior vertices. For
n
fixed, no matter what phylogenetic
X
-tree
T
is constructed, by Exercise
10.4
, the number of vertices
|
X
|=
is always the
same. Without loss of generality (that is, by relabeling the elements of
V
), it makes
sense to speak of an
ordering of cherries
or
cherry-picking order
as a sequence of
pairs of elements of
V
|
V
|
=[
2
n
−
2
]
(with, say, the elements of
X
⊂
V
corresponding
to
), for which the NJ Algorithm produces some binary phylogenetic
X
-tree
T
from
some input dissimilarity map
D
[
n
]
m
, by picking cherries according to
∈
R
σ
.
σ
⊂
,
|
|=
|
|=
−
For a cherry-picking order
on
V
, with
X
V
X
n
, and
V
2
n
2, for
n
2
,take
C
m
for which the NJ
m
=
to be the set of all dissimilarity maps
D
in
R
σ
Algorithm applied to
D
proceeds using
σ
. (The NJ Algorithm also outputs a weighting
ω
on
T
, but that's not important for the definition of
C
.) Applying Exercise
10.19
,if
σ
m
. This cone
D
∈
C
then
λ
D
∈
C
for any positivemultiple
λ
. Thus,
C
is a cone in
R
σ
σ
σ
m
is the union of NJ cones,
is called a
neighbor-joining (NJ) cone
. The entire space
R
running over all cherry-picking orderings
σ
.Take
C
T
to be the set of all dissimilarity
m
for which theNJ Algorithmoutputs the unrooted binary phylogenetic
X
-
maps
D
in
R
tree
T
=
(
V
,
E
)
∈
T
n
with some weighting
ω
. For each (binary) phylogenetic
X
-tree
=
T
∈
T
n
, one has
C
T
C
σ
for cherry-picking orders
σ
that are compatible with
T
.
σ
In some cases, a tree
T
∈
T
n
can arise frommore than one ordering, and in that case, the
boundaries of the corresponding NJ cones intersect. Neighbor-joining cones describe
Search WWH ::
Custom Search