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 Bipartite, 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 APXAPX-hard, even when the input consists of five uniquely leaf-labeled 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.
Complexity insights of the Minimum Duplication problem
DONDI, Riccardo;
2014-01-01
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 Bipartite, 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 APXAPX-hard, even when the input consists of five uniquely leaf-labeled 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.File | Dimensione del file | Formato | |
---|---|---|---|
TCS2014.pdf
Solo gestori di archivio
Descrizione: publisher's version - versione dell'editore
Dimensione del file
1.06 MB
Formato
Adobe PDF
|
1.06 MB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
Aisberg ©2008 Servizi bibliotecari, Università degli studi di Bergamo | Terms of use/Condizioni di utilizzo