Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Concept Videos

Gene Duplication and Divergence02:37

Gene 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.
Gene Families01:57

Gene 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...
Genome Copying Errors02:46

Genome Copying Errors

DNA replication is a well-evolved process that copies millions of base pairs with high fidelity during each cell division. Occasionally a wrong base or a long stretch of wrong bases may get added to the daughter strands. If the errors are left unchecked, cells might accumulate several mutations that might endanger their  survival. Therefore, the copying errors are checked and repaired at three levels.
Gene Conversion02:08

Gene Conversion

Other than maintaining genome stability via DNA repair, homologous recombination plays an important role in diversifying the genome. In fact, the recombination of sequences forms the molecular basis of genomic evolution. Random and non-random permutations of genomic sequences create a library of new amalgamated sequences. These newly formed genomes can determine the fitness and survival of cells. In bacteria, homologous and non-homologous types of recombination lead to the evolution of new...
Gene Conversion02:08

Gene Conversion

Other than maintaining genome stability via DNA repair, homologous recombination plays an important role in diversifying the genome. In fact, the recombination of sequences forms the molecular basis of genomic evolution. Random and non-random permutations of genomic sequences create a library of new amalgamated sequences. These newly formed genomes can determine the fitness and survival of cells. In bacteria, homologous and non-homologous types of recombination lead to the evolution of new...
Overview of Transposition and Recombination02:13

Overview of Transposition and Recombination

Transposons make up a significant part of genomes of various organisms. Therefore, it is believed that transposition played a major evolutionary role in speciation by changing genome sizes and modifying gene expression patterns. For example, in bacteria, transposition can lead to conferring antibiotic resistance. Movement of transposable elements within the genetic pool of pathogenic bacteria can aid in transfer of antibiotic-resistant genetic elements. In eukaryotes, transposons can carry out...

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

<i>Special Issue:</i> 13th International Conference on Computational Advances in Bio and Medical Sciences.

Journal of computational biology : a journal of computational molecular cell biology·2026
Same author

The Effect of Nephrology Referral on CKD Outcomes in Israel.

Clinical journal of the American Society of Nephrology : CJASN·2026
Same author

Demography-dependent variability in the human tumor mycobiome.

Microbiology spectrum·2026
Same author

Optimizing Parkinson's disease progression scales using computational methods.

NPJ Parkinson's disease·2026
Same author

HLA export by melanoma cells decoys cytotoxic T cells to promote immune evasion.

Cell·2025
Same author

ProFiT-SPEci-FISH: a novel approach for linking plasmids to hosts in complex microbial communities at the single-cell level.

Microbiome·2025

Related Experiment Video

Updated: Jun 9, 2026

Genome-wide Purification of Extrachromosomal Circular DNA from Eukaryotic Cells
14:26

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.

Mukul S Bansal1, Ron Shamir

  • 1School of Computer Science, Schreiber Bldg., Tel-Aviv University, Tel Aviv 69978, Israel. bansal@tau.ac.il

IEEE/ACM Transactions on Computational Biology and Bioinformatics
|August 25, 2010
PubMed
Summary

A flaw in a fixed-parameter algorithm for the gene-duplication problem is revealed, impacting its tractability. This discovery also links the problem to minimum rooted triplets inconsistency, showing it is W[2]-hard and difficult to approximate.

More Related Videos

Determination of the Optimal Chromosomal Location(s) for a DNA Element in Escherichia coli Using a Novel Transposon-mediated Approach
11:12

Determination of the Optimal Chromosomal Location(s) for a DNA Element in Escherichia coli Using a Novel Transposon-mediated Approach

Published on: September 11, 2017

Manipulation of Ploidy in Caenorhabditis elegans
07:54

Manipulation of Ploidy in Caenorhabditis elegans

Published on: March 15, 2018

Related Experiment Videos

Last Updated: Jun 9, 2026

Genome-wide Purification of Extrachromosomal Circular DNA from Eukaryotic Cells
14:26

Genome-wide Purification of Extrachromosomal Circular DNA from Eukaryotic Cells

Published on: April 4, 2016

Determination of the Optimal Chromosomal Location(s) for a DNA Element in Escherichia coli Using a Novel Transposon-mediated Approach
11:12

Determination of the Optimal Chromosomal Location(s) for a DNA Element in Escherichia coli Using a Novel Transposon-mediated Approach

Published on: September 11, 2017

Manipulation of Ploidy in Caenorhabditis elegans
07:54

Manipulation of Ploidy in Caenorhabditis elegans

Published on: March 15, 2018

Area of Science:

  • Computational Biology
  • Algorithm Analysis
  • Phylogenetics

Background:

  • The gene-duplication problem is crucial for reconciling gene trees with species trees.
  • A previous result suggested this problem is fixed-parameter tractable (FPT) concerning the number of gene duplications.
  • This FPT result has been a significant, yet potentially flawed, assumption in the field.

Purpose of the Study:

  • To identify and analyze an error in Stege's fixed-parameter algorithm for the gene-duplication problem.
  • To investigate the implications of this error on the problem's computational complexity and approximability.
  • To establish a connection between gene duplication and the minimum rooted triplets inconsistency problem.

Main Methods:

  • Algorithmic analysis to uncover flaws in the existing fixed-parameter algorithm.
  • Complexity theory, specifically W-hardness, to assess the problem's inherent difficulty.
  • Approximation algorithms and hardness results to evaluate the feasibility of finding near-optimal solutions.

Main Results:

  • An error in Stege's fixed-parameter algorithm for gene duplication is identified and proven uncorrectable without losing FPT.
  • The gene-duplication problem is shown to be W[2]-hard when parameterized by the number of duplications.
  • The problem is demonstrated to be hard to approximate within a logarithmic factor.

Conclusions:

  • The previously assumed fixed-parameter tractability of the gene-duplication problem is invalidated.
  • The gene-duplication problem possesses a higher degree of computational complexity than previously understood.
  • New theoretical bounds highlight significant challenges in both exact and approximate solutions for gene tree reconciliation.