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