Conference
Version
M. Gastaldello, T. Calamoneri, M.F. Sagot
Phylogenetic tree reconciliation is the approach commonly used to investigate the coevolution of sets of organisms such as hosts and symbionts. Given a phylogenetic tree for each such set, respectively denoted by H and S, together with a mapping ? of the leaves of S to the leaves of H, a reconciliation is a mapping ? of the internal vertices of S to the vertices of H which extends ? with some constraints. Given a cost for each reconciliation, a huge number of most parsimo- nious ones are possible, even exponential in the dimension of the trees. Without further information, any biological interpretation of the under- lying coevolution would require that all optimal solutions are enumerated and examined. The latter is however impossible without providing some sort of high level view of the situation. One approach would be to extract a small number of representatives, based on some notion of similarity or of equivalence between the reconciliations. In this paper, we define two equivalence relations that allow one to identify many reconciliations with a single one, thereby reducing their number. Extensive experiments indicate that the number of output solu- tions greatly decreases in general. By how much clearly depends on the constraints that are given as input.he structure of the set $LPG \cap mLPG$, proving that graphs with Dilworth number two belong to this intersection.
PDF Files