A 2-approximation for the minimum duplication speciation problem |
| |
Authors: | Ouangraoua A?da Swenson Krister M Chauve Cedric |
| |
Institution: | INRIA Lille-Nord Europe, LIFL, Université Lille 1, Villeneuve d' Ascq, France. Aida.Ouangraoua@inria.fr |
| |
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. |
| |
Keywords: | |
本文献已被 PubMed 等数据库收录! |
|