We consider how the orthology/paralogy information can be corrected in order to represent a gene tree, a problem that has recently gained interest in phylogenomics. Interestingly, the problem is related to the Minimum CoGraph Editing problem on the relation graph that represents orthology/paralogy information, where we want to minimize the number of edit operations on the given relation graph in order to obtain a cograph. In this paper we provide both theoretical and experimental results on the Minimum CoGraph Editing problem. On the theoretical side, we provide approximation algorithms for bounded degree relation graphs, for the general problem and for the problem restricted to deletion of edges. On the experimental side, we present a genetic algorithm for Minimum CoGraph Editing and we provide an experimental evaluation of the genetic algorithm on synthetic data.
Dondi, R., Mauri, G., & Zoppis, I. (2017). Orthology Correction for Gene Tree Reconstruction: Theoretical and Experimental Results. In Proc. ICCS 2017 – Int. Conf. on Computational Science (pp.1115-1124). Amsterdam : Elsevier B.V..
Citazione: | Dondi, R., Mauri, G., & Zoppis, I. (2017). Orthology Correction for Gene Tree Reconstruction: Theoretical and Experimental Results. In Proc. ICCS 2017 – Int. Conf. on Computational Science (pp.1115-1124). Amsterdam : Elsevier B.V.. |
Tipo: | slide + paper |
Carattere della pubblicazione: | Scientifica |
Presenza di un coautore afferente ad Istituzioni straniere: | No |
Titolo: | Orthology Correction for Gene Tree Reconstruction: Theoretical and Experimental Results |
Autori: | Dondi, R; Mauri, G; Zoppis, I |
Autori: | MAURI, GIANCARLO (Secondo) ZOPPIS, ITALO FRANCESCO (Ultimo) |
Data di pubblicazione: | 2017 |
Lingua: | English |
Nome del convegno: | International Conference on Computational Science ICCS June 12-14 |
Rivista: | PROCEDIA COMPUTER SCIENCE |
Appare nelle tipologie: | 02 - Intervento a convegno |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
C172-ICCS 2017.pdf | N/A | Open Access Visualizza/Apri |