Biology Reference
In-Depth Information
1.
Use the example file (under input data) to explore the option “Balanced GME.”
Note that one can click on “file” in “example file” to see the data, some of which
will be familiar from previous exercises. Results will be e-mailed back to you in
Newick format.
2.
Review [
15
] for a discussion of the success of this implementation versus the NJ
Algorithm.
Options in
FastME
also include implementations of the NJ Algorithm and its
improved version, the BioNJ Algorithm. There is a special reason why. Although
the NJ Algorithm was long a favorite among molecular and other biologists for its
effectiveness in practice, after many years of investigation, reservations about the NJ
Algorithm remained, due in part to an ongoing sense of uncertainty about just what the
algorithm was doing (and hence why it could be successful), from a more theoretical
perspective. Illumination came in the form of a result by [
29
] linking the BMEmethod
and NJ Algorithm by showing that the NJ Algorithm is a so-called greedy algorithm
for implementing the BME principle. Since the BME method is well grounded in
standard mathematical approaches (minimization problems), this link shed light on
the “true” nature of the NJ Algorithm. As a greedy algorithm, the NJ Algorithm acts
locally, however, and like any greedy algorithm, does not necessarily actually produce
atree
T
which is optimal for the BME principle (i.e., has total length
minimal).
The BME method for phylogenetic tree reconstruction can be reformulated still
further in a neat geometric way. By definition, a convex set
B
(say
B
ω(
T
)
m
)isonefor
⊂
R
m
that is on any line
which any point
z
∈
R
joining any two points
x
,
y
∈
B
is also in
B
, i.e.,
z
on
implies
z
∈
B
. It is an easy exercise to see that the intersection of any set
n
2
of convex sets is also convex. Let
B
n
be the convex hull in
of all the BME vectors
R
T
w
∈
T
n
; by definition, the convex hull of a set of points is the intersection of
all convex sets containing these points. This produces a polytope (analog of a polygon
for
T
n
2
in higher dimensional space), which we call the
nth BME polytope
.
As a consequence of the definition of the BME vectors and the BME method, the
vertices of the BME polytope are actually the BME vectors
B
n
,inside
R
T
∈
T
n
.Usingthe
generalized notion of BME vectors as in [
2
], the BME vector of the star phylogeny
lies in the interior of the BME polytope
w
,
T
B
n
, and all other BME vectors lie on the
boundary of the BME polytope.
Exercise 10.23.
Explain why
6
.
B
4
is just a triangle in
R
By Exercise
10.23
, the BME polytope for
n
=
4 is a familiar two-dimensional
n
2
object. More generally, the dimension of
B
n
=
−
n
.If
n
6, then thinking not
n
2
of the full polytope in
, but considering only vertices and edges of
B
n
alone,
R
there is a graph isomorphism between
B
n
and the complete graph on
n
vertices.
Search WWH ::
Custom Search