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

2009/04/10 by Cédric Chauve, Cedric Chauve, Chauve, Cedric +2
Agricultural and Biological Sciences · Biochemistry, Genetics and Molecular Biology · Computer Science · #Chromosomal and Genetic Variations #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Biological sciences #FOS: Computer and information sciences #Genome Rearrangement Algorithms #Genomics and Phylogenetic Studies #Quantitative Methods (q-bio.QM) #cs.DM #cs.DS #q-bio.QM

paper · pdf · doi:10.48550/arxiv.0904.1645

openalex publication_date 2009/04/10 · arxiv created 2009/04/15 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Related

• Minimizing the number of episodes and Gallai's theorem on intervals
• Species tree estimation under joint modeling of coalescence and duplication: sample complexity of quartet methods
• Polynomial-Time Algorithms for Phylogenetic Inference Problems involving duplication and reticulation
• Reconciling Multiple Genes Trees via Segmental Duplications and Losses
• From gene trees to species trees II: Species tree inference in the deep coalescence model