Biology Reference
In-Depth Information
and used to show that both NNI moves and SPR (subtree-pruning-and-regrafting)
moves between trees
T
∈
T
n
give rise to edges in the BME polytope. Since
FastME
uses NNI moves to heuristically implement the BMEmethod, Haws et al. [
23
] implies
that
FastME
is an edge-walk along the BME polytope. With better knowledge of
the BME polytope, it might be possible to find an even faster heuristic. Results in
[
23
] show that clades (subtrees obtained by taking all children of a parent node and
the edges that join them) correspond to “faces” in the BME polytope and identify
themselves with BME polytopes
B
n
.
Finally, as it was for NJ cones, it is possible to define BME cones. For any
T
B
k
values
k
n
inside
∈
T
n
,a
n
2
BME cone is simply the set of all
D
as in Eq.
10.4
is minimal.
Again, geometrically, the BME cone describes the BME method, for the cone for
T
consists of all
D
for which the BME method applied to
D
produces
T
(with weighting
∈
R
for which
ω(
T
)
n
2
ω
∈
T
n
,
although a given
D
may lie in more than one BME cone. A consequence in [
23
]ofthis
analysis, in combination with previous work on the NJ cones, is a further refinement
of the relationship between the relationship of NJ as a greedy algorithm for the BME
principle. In mathematical lingo, for any cherry-picking order
). As before,
is partitioned into the BME cones, running over all
T
R
, the intersection of
the NJ cone
C
T
,σ
and the BME cone for
T
has positive measure. In particular, this
shows that for
any
order of joining nodes to form a tree, there is a dissimilarity map
so that the NJ Algorithm returns the BME tree, a useful phylogenetic result. The
performance of the NJ Algorithm and BME method can be further analyzed through
studying these cones, and the implications of their differing geometries are explored
further in [
27
,
23
]. A complete characterization of edges of the BME polytope in terms
of tree operations remains an open question, however.
Also, in terms of further work, [
17
] studied how the BME method works when the
addition of an extra taxon (e.g., species) to a data set alters the structure of the optimal
phylogenetic tree. They characterized the behavior of the BME phylogenetics on such
data sets, using the BME polytopes and the BME cones which are the normal cones
of the BME polytope, as noted in [
27
]. A related study for another tree reconstruction
method, UPGMA, was carried out in [
30
].
σ
10.5
SUMMARY
Many open questions in the treatment given in this chapter of some distance-based
methods for phylogenetic tree reconstruction, via geometric and computational per-
spectives, remain. For example, giving a complete characterization of edges of the
BME polytope in terms of tree operations has yet to be done. Other opportunities for
further research include expanding from trees to networks, since it is known that trees
do not capture well several aspects of molecular biology, including hybridization.
Currently, distance-based methods have been superseded (at least in common use
by many biologists) by other approaches. These other approaches include maximum
Search WWH ::
Custom Search