Biology Reference
In-Depth Information
realizing trees as points, and pave theway for further study of the space of phylogenetic
trees from the view of polyhedral geometry.
There has been much work to understand distance-based methods, such as the
balanced minimum evolution method and neighbor-joining method. In 2002, Desper
and Gascuel introduced a balanced minimum evolution (BME) principle, based on a
branch length estimation scheme of Pauplin [
14
]. The guiding principle of minimum
evolution tree reconstruction methods is to return a tree whose total length (sum of
branch lengths) is minimal, given an input dissimilarity map. The BME method is a
special case of these distance-based methods wherein branch lengths are estimated
by a weighted least-squares method (in terms of the input dissimilarity map and the
tree in question) that puts more emphasis on shorter distances than longer ones. Each
labeled tree topology gives rise to a vector, called herein
the BME vector,
which is
obtained from Pauplin's formula.
Implementing, exploring, and better understanding the BME method have been
focal points of several recent works. The software
FastME
, developed by Desper
and Gascuel, heuristically optimizes the BME principle using nearest-neighbor inter-
changes (NNI) [
15
]. In simulations,
FastME
gives superior trees compared to other
distance-based methods, including one of biologists' most popular distance-based
methods, the Neighbor-Joining (NJ) Algorithm, developed by Saitou and Nei [
16
].
In 2000, Pauplin showed that the BME method is equivalent to optimizing a linear
function, the dissimilarity map, over the BME representations of binary trees, given
by the BME vectors [
14
]. Eickmeyer et. al. defined the
nth BME polytope
as the
convex hull of the BME vectors for all binary trees on a fixed number
n
of taxa.
Hence the BME method is equivalent to optimizing the input dissimilarity map (a
linear function), over a BME polytope. In 2010, Cueto and Matsen [
17
] studied how
the BME method works when the addition of an extra taxon 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
,
i.e., the normal cones of the BME polytope. We will discuss some details of BME
method and NJ method from the view of polyhedral geometry in Section
10.4
,again
opening the doors to further reading and review.
10.2
BASICS ON TREES AND PHYLOGENETIC TREES
Trees are ubiquitous objects in any theory in which branching processes occur. Most
generally, as a graph, a
tree T
is a directed, connected graph consisting of a
nonempty set of
vertices
(or
nodes
),
V
, and set of
edges
,
E
=
(
V
,
E
)
V
, inwhich there are
no cycles or loops. We will assume all our trees are finite, that is,
V
is a finite set. Each
edge
e
⊆
V
×
wherein, by defini-
tion,
a
is the
initial vertex
of
e
and
b
is the
terminal vertex
of
e
, so that
e
is drawn as the
arrow
a
∈
E
identifies with a single ordered pair
(
a
,
b
)(
a
=
b
)
→
b
, andwe also often say
e
starts at
a
and ends at
b
.Givenavertex
v
∈
V
,the
number of edges ending in
v
is the
indegree indeg
(v)
of
v
, while the number of edges
starting in
v
is the
outdegree outdeg
(v)
of
v
.The
leaves
of a tree
T
are those vertices
Search WWH ::
Custom Search