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.
Complete list of metadatas

Cited literature [30 references]  Display  Hide  Download
Contributor : Guillaume Blin <>
Submitted on : Tuesday, February 18, 2014 - 2:01:51 PM
Last modification on : Friday, April 12, 2019 - 10:18:09 AM
Long-term archiving on : Sunday, May 18, 2014 - 11:50:20 AM


Files produced by the author(s)


  • HAL Id : hal-00948488, version 1


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⟩



Record views


Files downloads