Parallel and Distributed Computation of Large Phylogenetic Trees - Parallel Computing for Bioinformatics and Computational Biology - page 328

In a computational context, phylogenetic trees are usually strictly bifurcating
(binary) unrooted trees. The organisms of the alignment are located at the tips
(leaves) of such a tree, whereas the inner nodes represent extinct common ancestors.
The branches of the tree represent the time that was required for the mutation of one
species into another, new, one. An example for the evolutionary tree of the monkeys
and the Homo sapiens is provided in Figure 14.1.
The inference of phylogenies with computational methods has many important
applications in medical and biological researches such as drug discovery and conser-
vation biology. A paper by Bader et al. [1] addresses potential industrial applications
of evolutionary tree inference and contains numerous useful references to important
biological results obtained by phylogenetic analyses.
Owing to the rapid growth of available sequence data over the last years and the
constant improvement of multiple alignment methods it has now become feasible to
compute very large trees, which comprise more than 1000 organisms. The compu-
tation of the tree-of-life containing representatives of all living beings on Earth is
considered to be one of the grand challenges in bioinformatics.
The main focus of this chapter is on algorithmic as well as technical problems and
solutions for the computation of large trees (containing

≥ 1000 sequences) based on

statistic models of sequence evolution.
The most fundamental algorithmic problem computational phylogeny faces
consists in the immense amount of potential alternative tree topologies. This number

Figure 14.1 Phylogenetic tree representing the evolutionary relationship between monkeys
and Homo sapiens.