Making sense of a cophylogeny output: Efficient listing of representative reconciliations
| Autor: | Wang, Yishu, Mary, Arnaud, Sagot, Marie-France, Sinaimeri, Blerina |
|---|---|
| Přispěvatelé: | 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), Libera Università Internazionale degli Studi Sociali Guido Carli [Roma] (LUISS), Carbone, Alessandra and El-Kebir, Mohammed |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
Cophylogeny
Dynamic programming Enumeration Equivalence relation Mathematics of computing → Graph enumeration Enumeration [SDV]Life Sciences [q-bio] Cophylogeny Equivalence relation Theory of computation → Dynamic programming [INFO.INFO-BI]Computer Science [cs]/Bioinformatics [q-bio.QM] Dynamic programming Theory of computation → Backtracking |
| Zdroj: | WABI 2021-21st International Workshop on Algorithms in Bioinformatics WABI 2021-21st International Workshop on Algorithms in Bioinformatics, Aug 2021, Chicago, United States. pp.1-18, ⟨10.4230/LIPIcs.WABI.2021.3⟩ |
| DOI: | 10.4230/LIPIcs.WABI.2021.3⟩ |
| Popis: | Cophylogeny reconciliation is a powerful method for analyzing host-parasite (or host-symbiont) co-evolution. It models co-evolution as an optimization problem where the set of all optimal solutions may represent different biological scenarios which thus need to be analyzed separately. Despite the significant research done in the area, few approaches have addressed the problem of helping the biologist deal with the often huge space of optimal solutions. In this paper, we propose a new approach to tackle this problem. We introduce three different criteria under which two solutions may be considered biologically equivalent, and then we propose polynomial-delay algorithms that enumerate only one representative per equivalence class (without listing all the solutions). Our results are of both theoretical and practical importance. Indeed, as shown by the experiments, we are able to significantly reduce the space of optimal solutions while still maintaining important biological information about the whole space. LIPIcs, Vol. 201, 21st International Workshop on Algorithms in Bioinformatics (WABI 2021), pages 3:1-3:18 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|