Biology Reference
In-Depth Information
m
is aweighted
tree with underlying topology
T
if and only if
D
is in the union of NJ cones
C
T
.
Example 10.7.
For an unrooted binary phylogenetic
X
-tree
T
theNJAlgorithmgeometrically—the output of theNJ on a point
D
∈
R
=
(
V
,
E
)
onaset
X
=
{
i
,
j
,
k
,,
b
}
of five leaves, one has
|
V
|=
8, and the orders of picking cherries in the
5
2
NJ Algorithm applied to any dissimilarity map
D
will consist of sequences
of pairs from
V
. Necessarily,
T
has two pairs of cherries, say
∈
R
{
i
,
j
}
and
{
k
,
}
, one
,v,w
∈
other leaf
b
, and three interior nodes
u
V
. In the NJ Algorithm, for any order
σ
of picking cherries
that yields
T
(with some weighting) the first cherry picked will
be either
{
i
,
j
}
or
{
k
,
}
. After this, if, say,
u
is the created ancestor node for
{
i
,
j
}
, then
either
a cherry to be picked. Once either cherry
is chosen, the other is completely determined for the next step, since there is only one
(binary, unrooted) tree topology for
n
{
k
,
}
is a cherry to be picked, or
{
u
,
b
}
=
5. Thus, for
T
∈
T
5
and cherries
{
i
,
j
}
and
{
k
,
}
, the NJ cones
C
, and
C
σ
are the same, for
σ
starting with the subsequence
σ
σ
starting with
{
i
,
j
}
,
{
u
,
b
}
,
{
k
,
l
}
and for
{
i
,
j
}
,
{
k
,
}
,
{
u
,
b
}
or
{
i
,
j
}
,
{
k
,
}
,
{
v,
b
}
,
where
and
σ
does yield different orders and cones. Thus, for any binary phylogenetic
X
tree
T
on
v
is the ancestor of
{
k
,
}
. Switching the order of
{
i
,
j
}
and
{
k
,
}
in
σ
5 leaves, there are two essentially distinct NJ cones which encompass
all dissimilarity maps
D
that output
T
;in[
26
] these are labelled
C
ij
,
b
, and
C
k
,
b
.
Consequently, there are 30
|
X
|=
5. For more details, see [
26
].
Neighbor-joining cones are defined and studied in detail for small trees (
n
=
15
·
2 total NJ cones for
n
=
6) in
[
26
]. By studying and comparing the volumes of the NJ cones, [
26
] can geometrically
formulate results about the behavior of the NJ Algorithm. These include how likely
the NJ Algorithm is to return a particular tree topology given a random input vector
(dissimilarity map), and the robustness of the NJ Algorithm. More complete informa-
tion about these NJ cones, including information about “dimensions” of the cones,
rays of the cones, faces, and other results, also appears in [
27
]. In both [
27
,
23
], geo-
metric information is used to gain further insight into a comparison between the NJ
Algorithm as a phylogenetic tree reconstruction method and another distance-based
method, the balanced minimum evolution (BME) method, a topic we now explore.
10.4.2
Balanced Minimum Evolution
Recall that for any set
|
X
|
with
|
X
|=
n
, and any edge-weighted phylogenetic
X
-tree
(
.
One can set the
total length of the tree
to be the total sum of all the edge weights:
ω(
T
,ω)
∈
T
n
, with
T
=
(
V
,
E
)
, there is a naturally associated tree metric
D
T
,ω
)
=
e
∈
E
ω(
.The
minimum evolution principle
for tree reconstruction uses
the idea of minimizing tree length in order to find the best-fitting tree
T
e
)
(
T
,ω)
∈
T
n
n
2
to a given dissimilarity map
D
∈
R
. Specifically, given a dissimilarity map
n
2
as input, a minimum evolution method seeks to locate as output an edge-
weighted tree
D
∈
R
is as small
as possible. Biologically, the minimum evolution principle is driven by the idea that
(
T
,ω)
so that
D
T
,ω
(
i
,
j
)
=
d
(
i
,
j
)
for all
i
,
j
∈
X
, and
ω(
T
)
Search WWH ::
Custom Search