Related Experiment Video
Updated: Jun 9, 2026

Genome-wide Purification of Extrachromosomal Circular DNA from Eukaryotic Cells
Published on: April 4, 2016
A Note on the Fixed Parameter Tractability of the Gene-Duplication Problem
1School of Computer Science, Schreiber Bldg., Tel-Aviv University, Tel Aviv 69978, Israel. bansal@tau.ac.il
Abstract:
The NP-hard gene-duplication problem takes as input a collection of gene trees and seeks a species tree that requires the fewest number of gene duplications to reconcile the input gene trees. An oft-cited, decade-old result by Stege states that the gene-duplication problem is fixed parameter tractable when parameterized by the number of gene duplications necessary for the reconciliation. Here, we uncover an error in this fixed parameter algorithm and show that this error cannot be corrected without sacrificing the fixed parameter tractability of the algorithm. Furthermore, we show a link between the gene-duplication problem and the minimum rooted triplets inconsistency problem which implies that the gene-duplication problem is 1) W[2]-hard when parameterized by the number of gene duplications necessary for the reconciliation and 2) hard to approximate to better than a logarithmic factor.
Related Concept Videos
Gene Duplication and Divergence
The duplicated copies of the gene are called Paralogs. Paralogs with similar sequences and functions form a gene family. Across several species, a large number of gene families are characterized.
Gene Families
Occasionally these regions can be adapted to take on new roles within the organism, becoming novel genes...
Genome Copying Errors
Gene Conversion
Gene Conversion
Overview of Transposition and Recombination

