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.

Beretta, S., & Dondi, R. (2016). Correcting Gene Trees by Leaf Insertions: Complexity and Approximation. ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 322, 35-50 [10.1016/j.entcs.2016.03.004].

Correcting Gene Trees by Leaf Insertions: Complexity and Approximation

BERETTA, STEFANO
Primo
;
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 in rivista - Articolo scientifico
Algorithms; Computational biology; Computational Complexity; Gene tree corrections; Gene Tree-Species Tree Reconciliation; Phylogenomics;
Algorithms; Computational biology; Computational Complexity; Gene tree corrections; Gene Tree-Species Tree Reconciliation; Phylogenomics; Theoretical Computer Science; Computer Science (all)
English
35
50
16
Beretta, S., & Dondi, R. (2016). Correcting Gene Trees by Leaf Insertions: Complexity and Approximation. ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 322, 35-50 [10.1016/j.entcs.2016.03.004].
Beretta, S; Dondi, R
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/10281/135346
Citazioni
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
Social impact