Skip to Main content Skip to Navigation
Journal articles

Co-divergence and tree topology

Abstract : 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.
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download
Contributor : Marie-France Sagot <>
Submitted on : Friday, September 27, 2019 - 9:10:02 AM
Last modification on : Tuesday, July 20, 2021 - 5:20:05 PM
Long-term archiving on: : Monday, February 10, 2020 - 4:54:56 AM


Files produced by the author(s)




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



Record views


Files downloads