Biology Reference
In-Depth Information
6.
Use the Newick input
(A,(B,(C,D)));
and the “Cladogram” and “Radial
(by Drawtree)” tree style options as in parts (1)-(5) above to create graphs of
rooted and unrooted trees. Examine also the outcome of permuting the leaves in
the Newick format.
7.
Repeat part (6) of this exercise, but with a Newick representation of a tree with
two pairs of cherries,
{
A
,
B
}
and
{
C
,
D
}
, with the rooted version having these
two pairs join in a common parent node.
8.
Apply the setting “Radial (by Drawtree)” (or just select the “Drawtree” program
directly) with the Newick input
(,(,));
and compare with part (5) of this
exercise.
Exercise 10.2.
Create other examples of a tree that is rooted and another that is
unrooted. List the indegrees, outdegrees, and degrees for the vertices in your trees, as
appropriate.
Exercise 10.3.
Given an arbitrary tree
T
, show that if a root of
T
exists, it is unique.
(If there is a root, there is only one root.)
An important means for comparing trees is that of an isomorphism. Directed trees
and
T
V
,
E
)
T
=
(
V
,
E
)
=
(
are
isomorphic
if they are isomorphic as graphs,
V
which extends to a bijection on the
meaning that there is a bijection
ϕ
:
V
→
E
,given
e
edges by setting
ϕ(
e
)
=
(ϕ(
a
), ϕ(
b
))
∈
=
(
a
,
b
)
∈
E
. Without loss of
T
for this isomorphism. Likewise, one may define
isomorphisms of undirected trees
T
generality, we write
ϕ
:
T
→
V
,
E
)
=
(
V
,
E
)
and
T
=
(
as bijections for
V
with
E
,for
e
ϕ
:
E
. Informally,
the notion of an isomorphism captures the idea that trees are like mobiles connecting
a set of objects, with edges that are springs. No matter how they are suspended by
a string from the ceiling, and no matter how they are stretched or spun about, if
they can be turned and their edges can be elongated or compressed so that the only
difference between mobiles is the particular choices of the objects dangling from the
ends (but not how many objects there are or the ways in which those objects are
hooked together), then the trees the mobiles represent are isomorphic. Accordingly,
isomorphisms of directed trees preserve the indegree and outdegree of each vertex,
so if
T
and
T
are isomorphic as directed trees, then
T
is rooted if and only if
T
is.
As we will focus on applications and representations of trees in phylogenetics, we
will be particularly interested in relationships between trees and their sets of leaves.
In this context, for a finite set
X
,a
phylogenetic X-tree
(rooted or unrooted) is a tree
T
V
→
ϕ(
{
a
,
b
}
)
={
ϕ(
a
), ϕ(
b
)
}∈
={
a
,
b
}∈
V
is the set of all leaves of
T
, and, by definition, its leaves
are labeled by
X
. That is, when pictured, the leaves are visibly labeled by the elements
of
X
, while interior nodes are left unlabeled. An alternative, more formal mathematical
formulation is to say that a phylogenetic
X
-tree is a pair
=
(
V
,
E
)
for which
X
⊂
(
T
,ψ)
consisting of a tree
T
V
,
but the informal idea will suffice. Although the interior vertices of a phylogenetic
X
-
tree are, by definition, unlabeled, inwhat follows, it will be helpful in several scenarios
to add labelings to interior nodes so as to describe or compare phylogenetic
X
-trees
that underlie these more fully labeled trees.
=
(
V
,
E
)
and a leaf-labeling
ψ
, which, by definition, is an injection
ψ
:
X
→
Search WWH ::
Custom Search