Gene tree correction has recently gained interest in phylogenomics, as it gives insights in understanding the evolution of gene families. Following some recent approaches based on leaf edit operations, we consider a variant of the problem where a gene tree is corrected by inserting leaves with labels in a multiset M. We show that the problem of deciding whether a gene tree can be corrected by inserting leaves with labels in M is NP-complete. Then, we consider an optimization variant of the problem that asks for the correction of a gene tree with leaves labeled by a multiset M′, with M′ ⊇ M, having minimum size. For this optimization variant of the problem, we present a factor 2 approximation algorithm.

(2016). Correcting gene trees by leaf insertions: complexity and approximation [journal article - articolo]. In ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE. Retrieved from http://hdl.handle.net/10446/78337

Correcting gene trees by leaf insertions: complexity and approximation

Dondi, Riccardo
2016

Abstract

Gene tree correction has recently gained interest in phylogenomics, as it gives insights in understanding the evolution of gene families. Following some recent approaches based on leaf edit operations, we consider a variant of the problem where a gene tree is corrected by inserting leaves with labels in a multiset M. We show that the problem of deciding whether a gene tree can be corrected by inserting leaves with labels in M is NP-complete. Then, we consider an optimization variant of the problem that asks for the correction of a gene tree with leaves labeled by a multiset M′, with M′ ⊇ M, having minimum size. For this optimization variant of the problem, we present a factor 2 approximation algorithm.
articolo
Beretta, Stefano; Dondi, Riccardo
(2016). Correcting gene trees by leaf insertions: complexity and approximation [journal article - articolo]. In ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE. Retrieved from http://hdl.handle.net/10446/78337
File allegato/i alla scheda:
File Dimensione del file Formato  
BerettaDondi_2016_GeneTrees.pdf

accesso aperto

Versione: publisher's version - versione editoriale
Licenza: Creative commons
Dimensione del file 264.16 kB
Formato Adobe PDF
264.16 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

Aisberg ©2008 Servizi bibliotecari, Università degli studi di Bergamo | Terms of use/Condizioni di utilizzo

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