Co-divergence and tree topology - Archive ouverte HAL Access content directly
Journal Articles Journal of Mathematical Biology Year : 2019

Co-divergence and tree topology

(1) , (1) , (2, 3)


In reconstructing the common evolutionary history of hosts and parasites, the current method of choice is the phylogenetic tree reconciliation. In this model, we are given a host tree H, a parasite tree P , and a function σ mapping the leaves of P to the leaves of H and the goal is to find, under some biologically motivated constraints, a reconciliation, that is a function from the vertices of P to the vertices of H that respects σ and allows the identification of biological events such as co-speciation, duplication and host switch. The maximum co-divergence problem consists in finding the maximum number of co-speciations in a reconciliation. This problem is NP-hard for arbitrary phylogenetic trees and no approximation algorithm is known. In this paper we consider the influence of tree topology on the maximum co-divergence problem. In particular we focus on a particular tree structure, namely caterpillar, and show that-in this case-the heuristics that are mostly used in the literature provide solutions that can be arbitrarily far from the optimal value. Then, we prove that finding the max co-divergence is equivalent to compute the maximum length of a subsequence with certain properties of a given permutation. This equivalence leads to two consequences: (i) it shows that we can compute efficiently in polynomial time the optimal time-feasible reconciliation and (ii) it can be used to understand how much the tree topology influences the value of the maximum number of co-speciations.
Fichier principal
Vignette du fichier
caterpillars_cophy_revision.pdf (549.84 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-02298643 , version 1 (27-09-2019)



Tiziana Calamoneri, Angelo Monti, Blerina Sinaimeri. Co-divergence and tree topology. Journal of Mathematical Biology, 2019, 79 (3), pp.1149-1167. ⟨10.1007/s00285-019-01385-w⟩. ⟨hal-02298643⟩
77 View
142 Download



Gmail Facebook Twitter LinkedIn More