Large-Scale Co-Phylogenetic Analysis on the Grid - Cloud, Grid and High Performance Computing: Emerging Applications - page 226

currently living organisms, roughly comparable
to a genealogical tree of species rather than indi-
vidual organisms. Phylogenetic trees or simply
phylogenies are typically unrooted binary trees.
The s organisms, which are represented by their
DNA or AA (Amino Acid/Protein) sequences
that are used as input data for the computation,
are located at the leave nodes (tips) of the tree
while the inner nodes of the topology represent
common extinct ancestors. There exist various
methods and models to reconstruct such trees
which differ in their computational complexity
and also in the accuracy of the final results, i.e.,
there exists a “classic” trade-off between speed and
accuracy. As already mentioned in the introduc-
tion, phylogenetic analysis has many important
applications in medical and biological research.
In Figure 1, we provide a simple example for the
phylogenetic tree of monkeys.
In the context of this article, however, we will
not address stand-alone phylogenetic inference,
but consider the problem of co-phylogenetic
analysis. Given two phylogenetic trees that rep-
resent the evolutionary histories of hosts and their

respective parasites, the “classic” example being
mammals and lice, and given the extant associa-
tions between the former and the latter, we want
to determine whether the parasite phylogeny is
more similar to the phylogeny of the respective
hosts than expected by chance alone. The main
interpretation of such a congruence between the
trees is that parasites have been associated with
respect to their evolutionary history and mostly
speciated in parallel (co-speciated) with their hosts
(Page, 2002). Given a parasite tree with n organ-
isms and a host tree with m organisms (sequenc-
es), their associations can be represented as a n
times m binary matrix, that contains information
of the type: does parasite x (x=1...n) occur or live
on host y (y=1...m) ? In addition to the question
of global congruence, one may also be interested
in whether individual associations significantly
increase the agreement between the phylogenies.
Such associations can be interpreted as being
caused mainly by co-speciation.
As previously mentioned, recent advances in
stand-alone phylogenetic inference methods in
combination with the increasing availability of

Figure 1. Phylogenetic tree of monkeys