A 3-approximation algorithm for computing a parsimonious first speciation in the gene duplication model

Simple item page
dc.creatorChauve, Cedric
dc.creatorOuangraoua, Aïda
dc.date2009-04-10
dc.date2009-04-15
dc.date.accessioned2026-07-07T13:03:38Z
dc.date.available2026-07-07T13:03:38Z
dc.descriptionWe consider the following problem: from a given set of gene families trees on a set of genomes, find a first speciation, that splits these genomes into two subsets, that minimizes the number of gene duplications that happened before this speciation. We call this problem the Minimum Duplication Bipartition Problem. Using a generalization of the Minimum Edge-Cut Problem, known as Submodular Function Minimization, we propose a polynomial time and space 3-approximation algorithm for the Minimum Duplication Bipartition Problem.
dc.identifierhttps://arxiv.org/abs/0904.1645
dc.identifierhttp://arxiv.org/abs/0904.1645
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/226872
dc.subjectDiscrete Mathematics
dc.subjectData Structures and Algorithms
dc.subjectQuantitative Methods
dc.titleA 3-approximation algorithm for computing a parsimonious first speciation in the gene duplication model
dc.typetext

Files

Collections

arXiv