title: A 2-approximation for the minimum duplication speciation problem.
abstract: We consider the following problem: given a set of gene family trees, spanning a given set of species, find a first speciation which splits these species into two subsets and 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, we propose a polynomial time 2-approximation algorithm for the Minimum Duplication Bipartition Problem. We apply this algorithm to the inference of species trees on synthetic datasets and on two datasets of eukaryotic species.
authors: INRIA Lille-Nord Europe, LIFL, Université Lille 1, Villeneuve d' Ascq, France. Aida.Ouangraoua@inria.fr
authors: Aïda
authors: A
authors: Ouangraoua
authors: Krister M
authors: KM
authors: Swenson
authors: Cedric
authors: C
authors: Chauve
mesh_terms: D000465:Algorithms; D003198:Computer Simulation; D056890:Eukaryota / Q000235:genetics; D019143:Evolution, Molecular; D049810:Genetic Speciation; D023281:Genomics; D008957:Models, Genetic; D010802:Phylogeny; D017422:Sequence Analysis, DNA / Q000379:methods*