Efficiently sparse listing of classes of optimal cophylogeny reconciliations

Abstract

Background: Cophylogeny reconciliation is a powerful method for analyzing host-parasite (or host-symbiont) co-evolution. It models co-evolution as an optimization problem where the set of all optimal solutions may represent different biological scenarios which thus need to be analyzed separately. Despite the significant research done in the area, few approaches have addressed the problem of helping the biologist deal with the often huge space of optimal solutions.

Results: In this paper, we propose a new approach to tackle this problem. We introduce three different criteria under which two solutions may be considered biologically equivalent, and then we propose polynomial-delay algorithms that enumerate only one representative per equivalence class (without listing all the solutions).

Conclusions: Our results are of both theoretical and practical importance. Indeed, as shown by the experiments, we are able to significantly reduce the space of optimal solutions while still maintaining important biological information about the whole space.

Keywords: Cophylogeny; Dynamic programming; Enumeration; Equivalence relation.

Fig. 1

Example of two reconciliations ${\varphi }_1$ and ${\varphi }_2$ on the same input. For each reconciliation, we draw the parasite tree on the left, the host tree on the right; the solid edges represent the associations for the leaf parasite nodes; the dashed edges represent the associations for the internal parasite nodes

Fig. 2

Example of a reconciliation graph for the input $(H,P,\sigma )$ in Fig. 1. Crossed circles are AND nodes. Rectangles are ${\text{OR}}^{+}$ nodes. The cells with which the ${\text{OR}}^{+}$ nodes are labeled are written inside. One solution subtree is shown in bold

Fig. 3

X-axis: All 46 instances (i.e. the pairs of datasets and cost vectors). Y-axis: In logarithmic scale, the Reduction value that is equal to the number of equivalence classes over the total number of reconciliations. For each instance, three points are plotted: the blue circle, the red triangle, and the black X, corresponding respectively to the V-, E-, and CD-equivalence relations. Four points of Reduction values less than ${10}^{-6}$ are omitted