Biology Reference
In-Depth Information
Fig. 12.
The branch-and-bound algorithm. The leaves of this decision tree
represent all possible complete phylogenetic tree topologies with 5 taxons. The
internal nodes represent incomplete phylogenetic tree topologies. The left sub-
tree has already been explored and an optimal tree length of 50 has been found
(shorter is better). Since the partial topology represented by the node in the
center of the figure already has a length of 54, the entire subtree (of the decision
tree) can only contain tree topologies with lengths greater than 54. Since the best
complete tree so far has a length of 50, it is not necessary to calculate the length
of the phylogenetic tree topology at each of the five leaves in the central part of
the decision tree.
incomplete tree is already longer than the shortest complete tree in
memory.
The search space of all possible phylogenetic trees can be represented
in the form of a decision tree (see Fig. 12). There is only one possible
topology for a three-taxon tree. Thus, if taxons are added one by one to
a phylogenetic tree, after the tree has reached a size of three taxons, a
decision must be made where to place each consecutive taxon as it is
added. This process is mirrored by a path from root to leaf in the deci-
sion tree. Each internal node of the tree (including the root) represents
a decision on where to place the next taxon in the phylogenetic tree.
Depending on the chosen position, the corresponding branch in the
decision tree is followed. Thus, the leaves of the decision tree represent
all possible tree topologies.
Since the inclusion of additional taxons to a partial tree can only
make the tree longer (and thus decrease the score), a lower bound for
tree score is given by the score of a partial tree corresponding
to an internal node of the decision tree. If this score is already worse than
that of the best complete tree found so far, then the subtree of the deci-
sion tree can be eliminated from the search space in a single step.
