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 metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/hal-02298643
Contributor : Marie-France Sagot <>
Submitted on : Friday, September 27, 2019 - 9:10:02 AM
Last modification on : Tuesday, November 19, 2019 - 2:47:10 AM

File

caterpillars_cophy_revision.pd...
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

36

Files downloads

304