Complexity Insights of the Minimum Duplication ProblemReport as inadecuate

Complexity Insights of the Minimum Duplication Problem - Download this document for free, or read online. Document in PDF available to download.

* Corresponding author 1 LIGM - Laboratoire d-Informatique Gaspard-Monge 2 DISCo - Dipartimento di Informatica Sistemistica e Comunicazione 3 Dipartimento di Scienze dei Linguaggi, della Comunicazione e degli Studi Culturali 4 Dipartimento di Informatica Verona 5 LAMSADE - Laboratoire d-analyse et modélisation de systèmes pour l-aide à la décision

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.

Author: Guillaume Blin - Paola Bonizzoni - Riccardo Dondi - Romeo Rizzi - Florian Sikora -



Related documents