Traversing the tangle: Algorithms and applications for cophylogenetic studies

Cophylogenetic analysis supposes that two or more phylogenetic trees for linked groups have been constructed, and explores the relationships the trees have with each other. These types of analyses are most commonly used to assess relationships between hosts and their parasites, however the methodology can also be applied to diverse types of problems such as an examination of the phylogenies of genes with respect to those of organisms or those of geographic areas and the organisms that reside there. The working hypothesis is that the trees are correct, though sometimes attempts are made to take into account their uncertainty. Cophylogeny is computationally hard: that is, there are no known fast methods to compute relationships among such trees for any but the simplest of models. A review of methodology that has been developed to examine cophylogenetic relationships is presented and a brief discussion of some medically relevant examples is given.