Background: 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. Results: 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). Conclusions: 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.

Efficiently sparse listing of classes of optimal cophylogeny reconciliations / Wang, Yishu; Mary, Arnaud; Sagot, Marie-France; Sinaimeri, Blerina. - In: ALGORITHMS FOR MOLECULAR BIOLOGY. - ISSN 1748-7188. - 17:1(2022), pp. 2-16. [10.1186/s13015-022-00206-y]

Efficiently sparse listing of classes of optimal cophylogeny reconciliations

Sinaimeri, Blerina
2022

Abstract

Background: 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. Results: 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). Conclusions: 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.
Cophylogeny, Dynamic programming, Enumeration, Equivalence relation
Efficiently sparse listing of classes of optimal cophylogeny reconciliations / Wang, Yishu; Mary, Arnaud; Sagot, Marie-France; Sinaimeri, Blerina. - In: ALGORITHMS FOR MOLECULAR BIOLOGY. - ISSN 1748-7188. - 17:1(2022), pp. 2-16. [10.1186/s13015-022-00206-y]
File in questo prodotto:
File Dimensione Formato  
s13015-022-00206-y.pdf

Open Access

Tipologia: Versione dell'editore
Licenza: Creative commons
Dimensione 2.01 MB
Formato Adobe PDF
2.01 MB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11385/215455
Citazioni
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact