An improved node mapping algorithm for the cophylogeny reconstruction problem

The cophylogeny reconstruction problem is central in the inference of ancient relationships among ecologically linked groups of organisms. Although it is known to be NP-Complete, there have been several heuristics proposed that often find good solutions. One such approach is to fix the order of the internal nodes of the host phylogeny and use dynamic programming to recover an optimal reconstruction in polynomial time. A meta-heuristic framework is then leveraged to iterate over the factorial set of fixed node orderings. The original solution used a technique known as node mapping, taking and was designed to handle phylogenetic networks. There has since been a number of implementations for this problem which use specific properties of phylogenetic trees to reduce their running time. In this paper, we introduce a set of new optimisation techniques to achieve a running time improvement matching these cubic time algorithms, while using node mapping, and discuss how these newly proposed optimisation techniques may lead to an improvement in the generalised case of phylogenetic networks and provide valuable insights into how to construct an optimized algorithm for handling evolutionary systems with widespread parasites.