Complexity Insights of the Minimum Duplication Problem

Abstract : The Minimum Duplication problem is a well-known problem in phylogenetics and comparative genomics. Given a set of gene trees, the Minimum Duplication problem asks for a species tree that induces the minimum number of gene duplications in the input gene trees. Recently, a variant of the Minimum Duplication problem, called Minimum Duplication Bi-partite, has been introduced, where the goal is to find all pre-duplications, that is duplications that in the evolution precede the first speciation with respect to a species tree. In this paper, we investigate the complexity of both Minimum Duplication and Minimum Duplication Bipartite. First of all, we prove that the Minimum Duplication problem is APX-hard, even when the input consists of five uniquely leaf-labelled gene trees (improving upon known results on the complexity of the problem). Then, we show that the Minimum Duplication Bipartite problem can be solved efficiently with a randomized algorithm when the input gene trees have bounded depth. An extended abstract of this paper appeared in SOFSEM 2012.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2014, 530, pp.66-79
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger

https://hal-upec-upem.archives-ouvertes.fr/hal-00948488
Contributeur : Guillaume Blin <>
Soumis le : mardi 18 février 2014 - 14:01:51
Dernière modification le : jeudi 5 juillet 2018 - 14:46:16
Document(s) archivé(s) le : dimanche 18 mai 2014 - 11:50:20

Fichier

article.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00948488, version 1

Citation

Guillaume Blin, Paola Bonizzoni, Riccardo Dondi, Romeo Rizzi, Florian Sikora. Complexity Insights of the Minimum Duplication Problem. Theoretical Computer Science, Elsevier, 2014, 530, pp.66-79. 〈hal-00948488〉

Partager

Métriques

Consultations de la notice

358

Téléchargements de fichiers

162