Related Experiment Video
Updated: Jun 23, 2026

Following the Dynamics of Structural Variants in Experimentally Evolved Populations
Published on: February 3, 2023
The gene-duplication problem: near-linear time algorithms for NNI-based local searches
Mukul S Bansal1, Oliver Eulenstein, André Wehe
1Department of Computer Science, Iowa StateUniversity, Ames, IA 50011, USA. bansal@cs.iastate.edu
Abstract:
The gene-duplication problem is to infer a species supertree from a collection of gene trees that are confounded by complex histories of gene-duplication events. This problem is NP-complete and thus requires efficient and effective heuristics. Existing heuristics perform a stepwise search of the tree space, where each step is guided by an exact solution to an instance of a local search problem. A classical local search problem is the {\tt NNI} search problem, which is based on the nearest neighbor interchange operation. In this work, we 1) provide a novel near-linear time algorithm for the {\tt NNI} search problem, 2) introduce extensions that significantly enlarge the search space of the {\tt NNI} search problem, and 3) present algorithms for these extended versions that are asymptotically just as efficient as our algorithm for the {\tt NNI} search problem. The exceptional speedup achieved in the extended {\tt NNI} search problems makes the gene-duplication problem more tractable for large-scale phylogenetic analyses. We verify the performance of our algorithms in a comparison study using sets of large randomly generated gene trees.
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...
Gene Evolution - Fast or Slow?
In contrast, regions which code...
Gene Evolution - Fast or Slow?
In contrast, regions which code...
Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
Exon Recombination
Exon shuffling follows “splice frame rules.” Each exon has three reading...

