Skip to Main content Skip to Navigation
Conference papers

Complexity Insights of the Minimum Duplication Problem

Abstract : Abstract. The Minimum Duplication problem is a well-known prob- lem 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. More recently, a variant of the Minimum Duplication problem, called Minimum Duplication Bipartite, has been introduced in [14], where the goal is to find all pre-duplications, that is duplications that precede, in the evolution, the first speciation with respect to a species tree. In this paper, we investigate the complexity of both Minimum Duplication and Minimum Duplication Bipartite problems. 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 (progressing on the complexity of the problem). Then, we show that the Minimum Duplication Bipartite problem can be solved efficiently by a randomized algorithm when the input gene trees have bounded depth.
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00629047
Contributor : Guillaume Blin <>
Submitted on : Tuesday, October 4, 2011 - 6:27:17 PM
Last modification on : Wednesday, February 26, 2020 - 7:06:06 PM
Long-term archiving on: : Thursday, March 30, 2017 - 4:25:47 PM

File

hal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00629047, version 1

Citation

Guillaume Blin, Paola Bonizzoni, Riccardo Dondi, Romeo Rizzi, Florian Sikora. Complexity Insights of the Minimum Duplication Problem. 38th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2012), Jan 2012, Špindleruv Mlýn, Czech Republic. pp.153-164. ⟨hal-00629047⟩

Share

Metrics

Record views

564

Files downloads

479