Co-divergence and tree topology

Autor: Angelo Monti, Tiziana Calamoneri, Blerina Sinaimeri
Přispěvatelé: Department of Informatics and System Sciences (Sapienza University of Rome), Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome] (UNIROMA), Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale (ERABLE), Inria Grenoble - Rhône-Alpes, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Baobab, Département PEGASE [LBBE] (PEGASE), Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire de Biométrie et Biologie Evolutive - UMR 5558 (LBBE), Université de Lyon-Université de Lyon-Institut National de Recherche en Informatique et en Automatique (Inria)-VetAgro Sup - Institut national d'enseignement supérieur et de recherche en alimentation, santé animale, sciences agronomiques et de l'environnement (VAS)-Centre National de la Recherche Scientifique (CNRS), Università degli Studi di Roma 'La Sapienza' = Sapienza University [Rome]
Rok vydání: 2018
Předmět:
Zdroj: Journal of Mathematical Biology
Journal of Mathematical Biology, 2019, 79 (3), pp.1149-1167. ⟨10.1007/s00285-019-01385-w⟩
Journal of Mathematical Biology, Springer Verlag (Germany), 2019, 79 (3), pp.1149-1167. ⟨10.1007/s00285-019-01385-w⟩
ISSN: 1432-1416
0303-6812
DOI: 10.1007/s00285-019-01385-w⟩
Popis: 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 [Formula: see text] 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 [Formula: see text] 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: (1) it shows that we can compute efficiently in polynomial time the optimal time-feasible reconciliation and (2) it can be used to understand how much the tree topology influences the value of the maximum number of co-speciations.
Databáze: OpenAIRE
Externí odkaz: