Biomedical Engineering Reference
In-Depth Information
Fig. 8.2
An evolutionary
process and its projection
onto the “now” plane - from
Cavalli-Sforza and
Edwards [
15
]
The authors first considered the problem of how to represent formally a
projection (phylogeny) of the evolutionary process. In order to remark the lack
of a direction in evolution, the authors proposed to remove the root and the orien-
tation in the edges of a phylogeny and represented it as an unrooted binary tree,
i.e., an undirected acyclic graph in which each internal vertex has degree three. The
degree constraint has not necessarily a biological foundation but helped the authors
to formalize the evolutionary process. In fact, given
n
taxa, the degree constraint
T
.2n 3/
implies that the number of edges in a phylogeny
is
and the number of
.n 2/
T
internal vertices is
. To prove the claim note that as
is a tree, it holds that:
j
E
i
.T /jCj
E
e
.T /jDjV
i
jCjV
e
j1;
(8.10)
where
, respectively.
Moreover, since internal vertices have degree three, the following property holds:
E
e
.T /
and
E
i
.T /
are the set of external and internal edges of
T
2j
E
i
.T /jC2j
E
e
.T /jD3jV
i
jCjV
e
j:
(8.11)
Combining (
8.10
)and(
8.11
) it follows that
jV
i
jD.n 2/
and
j
E
i
jD.n 3/
. Thus,
a phylogeny
T 2
T
can be seen as an unrooted binary tree in which the
n
taxa
are the
and the common ancestors are internal vertices of degree
three. It is worth noting that dealing with unrooted binary trees does not introduces
oversimplifications since it is easy to see that any
n
leaves of
T
-ary tree can be transformed into
a phylogeny by adding “dummy” vertices and edges (e.g., see Fig.
8.3
).
Cavalli-Sforza and Edwards encoded a phylogeny in
m
by means of an
Edge-
Path incidence matrix of a Tree
(EPT) (see [
53
, p. 550]) i.e., a network matrix
X
having a row for each path between two leaves and a column for each edge.
T
Search WWH ::
Custom Search