Biology Reference
In-Depth Information
cherry
{
x
,w
}
having parent node
u
and cherry
{
y
,
z
}
having parent node
v
,
suppose
d
H
(
u
,v)
=
1
,
d
H
(
u
,w)
=
1
=
d
H
(v,
z
)
, and
d
H
(
x
,
u
)
=
5
=
d
H
(v,
y
)
, with corresponding edge weight
ω
. (That is, if
e
=
(
i
,
j
),
i
,
j
∈
V
=
{
x
,
y
,w,
z
,
u
,v
}
, is an edge, we let
ω(
e
)
=
d
H
(
i
,
j
)
.)
a.
Would the parsimony method applied to
T
with
ω
reconstruct this tree?
Explain your answer.
b.
At least how many characters long would the sequences
s
i
,
∈
i
X
,haveto
be to create a tree
T
with the given edge-weightings?
3.
If
D
is a dissimilarity map on
X
for
|
X
|=
4, is
D
necessarily equal to
D
T
,ω
for
some choice of quartet
T
and some edge-weighting
ω
?
10.3.3
Tree Metrics and Tree Space
Dissimilarity maps
D
for which there is
some
labeled tree
T
and
some
nonnegative
edge-weighting
ω
for
T
such that
D
=
D
T
,ω
are called
tree metrics
.
Exercise 10.15.
a.
Show that a tree metric is necessarily a metric.
b.
Show that every tree metric satisfies the four-point condition.
These results lead, in part, to a fundamental characterization theorem of tree
metrics:
Theorem 10.1.
1.
A dissimilarity map D on a set X is a tree metric if and only if D satisfies the
four-point condition.
2.
If a dissimilarity map D on a set X is a tree metric for some
ω
edge-weighted tree
on X, and likewise for an X-tree T
=
(
V
,
E
)
T
and edge-weighting
ω
on T, then T and T
are isomorphic phylogenetic trees. Moreover, for
=
(
V
,
E
)
ϕ
:
T
→
T
an isomorphism, for any edge e
E,if e
=
ϕ(
ω
(
e
)
=
ω(
∈
e
)
, then
e
)
.
Part (2) of Exercise
10.15
gives one half of part (1) of Theorem
10.1
, showing
how to recognize tree metrics out of all possible dissimilarity maps; for a proof, see,
e.g., [
2
, Theorem 7.2.6]. Part (2) of Theorem
10.1
shows that any dissimilarity map
which is a tree metric for a phylogenetic
X
-tree not only comes from such a tree, but
corresponds to essentially one and only one pair
(
T
,ω)
of a phylogenetic
X
-tree and
edge-weighting
on
T
;see[
2
, Theorem 7.1.8] and its proof. Part (2) of Theorem
10.1
implies that tree metrics on
X
correspond exactly to edge-weighted phylogenetic
trees on
X
.
If a given dissimilarity map
D
onaset
X
is in fact a tree metric, then by definition,
there is a tree and an edge weighting that fits
D
exactly. As previously noted, in
general, evolutionary distance data
D
from real sequence data for species, genes,
etc., is noisy, and in our new language, although
D
will be a dissimilarity map,
D
will usually not already be a tree metric. Consequently, one looks for ways to find a
ω
Search WWH ::
Custom Search