Biology Reference
In-Depth Information
Chapter 12
Phylogenetic Tree Building Methods
Manuel Gil and Gaston H. Gonnet
1. Introduction
Phylogenetic tree construction, from given data, is a well-defined prob-
lem that is taken as a basic building block in bioinformatics. A phyloge-
netic tree is a hierarchical representation of some source data. The leaves
of a tree represent present-day objects (genes, species), and the internal
nodes represent common ancestors. A tree is generally n -ary, i.e. the
internal nodes can have any number of descendants, although there is no
loss of generality representing them as binary trees. From now on, we
will consider all our trees binary. A tree can be rooted or unrooted. The
root is the place of the common ancestor of all leaves. Most tree recon-
struction methods are not able to determine the root and produce
unrooted trees. It can be shown 1 that the number of unrooted leaf-
labeled tree topologies with n leaves is
3
×
5
×
7
×
×
(2 n
5).
While for five leaves there are 105 trees, already for 50 leaves the
number explodes to about 2.84
10 74 . a The goal of phylogenetic tree
construction is to find the tree in the tree space that describes the relation
between a given set of input data points as best as possible. It is normally
difficult or impossible to obtain data for the internal nodes of the tree.
×
a The number of atoms in the universe is estimated to be about 10 80 .
329
Search WWH ::




Custom Search