Complexity Insights of the Minimum Duplication Problem. Blin, G., Bonizzoni, P., Dondi, R., Rizzi, R., & Sikora, F. In Proc. of Current Trends in Theory and Practice of Computer Science (SOFSEM 2012), volume 7147, of Lect Notes Comput Sci, pages 153–164, 2012. Springer, Berlin. ![Complexity Insights of the Minimum Duplication Problem [link]](https://bibbase.org/img/filetypes/link.svg "link")
Paper doi abstract bibtex 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. 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.
@InProceedings{blin12complexity,
author = {Blin, Guillaume and Bonizzoni, Paola and Dondi, Riccardo and Rizzi, Romeo and Sikora, Florian},
title = {Complexity Insights of the Minimum Duplication Problem},
booktitle = {Proc. of Current Trends in Theory and Practice of Computer Science (SOFSEM 2012)},
year = {2012},
volume = {7147},
series = lncs,
pages = {153--164},
publisher = Springer,
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. 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.},
doi = {10.1007/978-3-642-27660-6_13},
keywords = {jena; fpt; PABI},
opteditor = {M{\'a}ria Bielikov{\'a} and Gerhard Friedrich and Georg Gottlob and Stefan Katzenbeisser and Gy{\"o}rgy Tur{\'a}n},
owner = {florian},
timestamp = {2011.10.11},
url = {http://hal-univ-mlv.archives-ouvertes.fr/hal-00629047/en/},
}
Downloads: 0
{"_id":"AmtTkB4vcgPbCStvS","bibbaseid":"blin-bonizzoni-dondi-rizzi-sikora-complexityinsightsoftheminimumduplicationproblem-2012","authorIDs":[],"author_short":["Blin, G.","Bonizzoni, P.","Dondi, R.","Rizzi, R.","Sikora, F."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"propositions":[],"lastnames":["Blin"],"firstnames":["Guillaume"],"suffixes":[]},{"propositions":[],"lastnames":["Bonizzoni"],"firstnames":["Paola"],"suffixes":[]},{"propositions":[],"lastnames":["Dondi"],"firstnames":["Riccardo"],"suffixes":[]},{"propositions":[],"lastnames":["Rizzi"],"firstnames":["Romeo"],"suffixes":[]},{"propositions":[],"lastnames":["Sikora"],"firstnames":["Florian"],"suffixes":[]}],"title":"Complexity Insights of the Minimum Duplication Problem","booktitle":"Proc. of Current Trends in Theory and Practice of Computer Science (SOFSEM 2012)","year":"2012","volume":"7147","series":"Lect Notes Comput Sci","pages":"153–164","publisher":"Springer, Berlin","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. 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.","doi":"10.1007/978-3-642-27660-6_13","keywords":"jena; fpt; PABI","opteditor":"Mária Bieliková and Gerhard Friedrich and Georg Gottlob and Stefan Katzenbeisser and György Turán","owner":"florian","timestamp":"2011.10.11","url":"http://hal-univ-mlv.archives-ouvertes.fr/hal-00629047/en/","bibtex":"@InProceedings{blin12complexity,\n author = {Blin, Guillaume and Bonizzoni, Paola and Dondi, Riccardo and Rizzi, Romeo and Sikora, Florian},\n title = {Complexity Insights of the Minimum Duplication Problem},\n booktitle = {Proc. of Current Trends in Theory and Practice of Computer Science (SOFSEM 2012)},\n year = {2012},\n volume = {7147},\n series = lncs,\n pages = {153--164},\n publisher = Springer,\n 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. 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.},\n doi = {10.1007/978-3-642-27660-6_13},\n keywords = {jena; fpt; PABI},\n opteditor = {M{\\'a}ria Bielikov{\\'a} and Gerhard Friedrich and Georg Gottlob and Stefan Katzenbeisser and Gy{\\\"o}rgy Tur{\\'a}n},\n owner = {florian},\n timestamp = {2011.10.11},\n url = {http://hal-univ-mlv.archives-ouvertes.fr/hal-00629047/en/},\n}\n\n","author_short":["Blin, G.","Bonizzoni, P.","Dondi, R.","Rizzi, R.","Sikora, F."],"key":"blin12complexity","id":"blin12complexity","bibbaseid":"blin-bonizzoni-dondi-rizzi-sikora-complexityinsightsoftheminimumduplicationproblem-2012","role":"author","urls":{"Paper":"http://hal-univ-mlv.archives-ouvertes.fr/hal-00629047/en/"},"keyword":["jena; fpt; PABI"],"metadata":{"authorlinks":{}}},"bibtype":"inproceedings","biburl":"https://git.bio.informatik.uni-jena.de/fleisch/literature/raw/master/group-literature.bib","creationDate":"2019-11-19T16:29:35.095Z","downloads":0,"keywords":["jena; fpt; pabi"],"search_terms":["complexity","insights","minimum","duplication","problem","blin","bonizzoni","dondi","rizzi","sikora"],"title":"Complexity Insights of the Minimum Duplication Problem","year":2012,"dataSources":["C5FtkvWWggFfMJTFX"]}