Related Experiment Video
Updated: Jun 23, 2026
04:52
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
Summary
This study introduces faster algorithms for the gene-duplication problem, improving phylogenetic tree inference. New methods speed up the Nearest Neighbor Interchange search, making large-scale analyses more feasible.
Area of Science:
- Computational Biology
- Phylogenetics
- Bioinformatics
Background:
- The gene-duplication problem is crucial for inferring species supertrees from gene trees.
- Gene trees are often complicated by gene duplication events, making this problem NP-complete.
- Existing heuristics rely on stepwise tree space searches guided by local problem solutions.
Purpose of the Study:
- To develop efficient heuristics for the gene-duplication problem.
- To improve the speed and scope of phylogenetic analyses.
- To address the computational complexity of inferring species supertrees.
Main Methods:
- Developed a novel near-linear time algorithm for the Nearest Neighbor Interchange (NNI) search problem.
- Introduced extensions to the NNI search problem to broaden the search space.
- Designed asymptotically efficient algorithms for these extended NNI versions.
Main Results:
- Achieved a significant speedup in solving extended NNI search problems.
- Demonstrated the enhanced tractability of the gene-duplication problem for large datasets.
- Validated algorithm performance through comparative studies on randomly generated gene trees.
Conclusions:
- The novel algorithms offer substantial performance improvements for phylogenetic inference.
- Extended NNI search strategies enhance the ability to handle complex gene histories.
- These advancements facilitate more robust and scalable phylogenetic analyses.
Related Concept Videos
02:37Gene Duplication and Divergence
The seminal work of Ohno in 1970 popularized the idea of gene duplication and divergence. DNA sequence comparison studies reveal that a large portion of the genes in bacteria, archaebacteria, and eukaryotes was generated by gene duplication and divergence, indicating its critical role in evolution.
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.
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.
01:57Gene Families
Gene families consist of groups of genes proposed to have originated from a common ancestor. Typically these arise through events in which a gene or genes are mistakenly duplicated during cell division. Unlike their parent genes (which are subject to selection pressure to maintain function), these gene copies do not need to preserve their sequences and may evolve at a relatively faster rate.
Occasionally these regions can be adapted to take on new roles within the organism, becoming novel genes...
Occasionally these regions can be adapted to take on new roles within the organism, becoming novel genes...
02:05Gene Evolution - Fast or Slow?
The genomes of eukaryotes are punctuated by long stretches of sequence which do not code for proteins or RNAs. Although some of these regions do contain crucial regulatory sequences, the vast majority of this DNA serves no known function. Typically, these regions of the genome are the ones in which the fastest change, in evolutionary terms, is observed, because there is typically little to no selection pressure acting on these regions to preserve their sequences.
In contrast, regions which code...
In contrast, regions which code...
02:05Gene Evolution - Fast or Slow?
The genomes of eukaryotes are punctuated by long stretches of sequence which do not code for proteins or RNAs. Although some of these regions do contain crucial regulatory sequences, the vast majority of this DNA serves no known function. Typically, these regions of the genome are the ones in which the fastest change, in evolutionary terms, is observed, because there is typically little to no selection pressure acting on these regions to preserve their sequences.
In contrast, regions which code...
In contrast, regions which code...
01:29Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
Mechanistic models play a crucial role in algorithms for numerical problem-solving, particularly in nonlinear mixed effects modeling (NMEM). These models aim to minimize specific objective functions by evaluating various parameter estimates, leading to the development of systematic algorithms. In some cases, linearization techniques approximate the model using linear equations.
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
02:32Exon Recombination
The evolution of new genes is critical for speciation. Exon recombination, also known as exon shuffling or domain shuffling, is an important means of new gene formation. It is observed across vertebrates, invertebrates, and in some plants such as potatoes and sunflowers. During exon recombination, exons from the same or different genes recombine and produce new exon-intron combinations, which might evolve into new genes.
Exon shuffling follows “splice frame rules.” Each exon has three reading...
Exon shuffling follows “splice frame rules.” Each exon has three reading...