Complexity Insights of the Minimum Duplication Problem - Archive ouverte HAL Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 2014

Complexity Insights of the Minimum Duplication Problem

Résumé

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.
Fichier principal
Vignette du fichier
article.pdf (803.15 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00948488 , version 1 (18-02-2014)

Identifiants

  • HAL Id : hal-00948488 , version 1

Citer

Guillaume Blin, Paola Bonizzoni, Riccardo Dondi, Romeo Rizzi, Florian Sikora. Complexity Insights of the Minimum Duplication Problem. Theoretical Computer Science, 2014, 530, pp.66-79. ⟨hal-00948488⟩
326 Consultations
217 Téléchargements

Partager

Gmail Facebook X LinkedIn More