A 3-approximation algorithm for computing a parsimonious first speciation in the gene duplication modelReportar como inadecuado




A 3-approximation algorithm for computing a parsimonious first speciation in the gene duplication model - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

* Corresponding author 1 Department of Mathematics Burnaby 2 LaBRI - Laboratoire Bordelais de Recherche en Informatique

Abstract : We 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.

Keywords : Gene duplication Phylogenomics Parsimony Algorithm Approximation





Autor: Cedric Chauve - Aïda Ouangraoua -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados