Related Experiment Video
Updated: Jun 28, 2026

G2-seq: A High Throughput Sequencing-based Technique for Identifying Late Replicating Regions of the Genome
Published on: March 22, 2018
An Omega(n2/ log n) speed-up of TBR heuristics for the gene-duplication problem
Mukul S Bansal1, Oliver Eulenstein
1Department of Computer Science, Iowa State University, Ames, IA 50011, USA.
Abstract:
The gene-duplication problem is to infer a species supertree from gene trees that are confounded by complex histories of gene duplications. This problem is NP-hard 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. We improve on the time complexity of the local search problem by a factor of n2= log n, where n is the size of the resulting species supertree. Typically, several thousand instances of the local search problem are solved throughout a stepwise heuristic search. Hence, our improvement makes the gene-duplication problem much more tractable for large-scale phylogenetic analyses.
More Related Videos
07:35Rapid, Enzymatic Methods for Amplification of Minimal, Linear Templates for Protein Prototyping using Cell-Free Systems
Published on: June 14, 2021
11:12Determination of the Optimal Chromosomal Location(s) for a DNA Element in Escherichia coli Using a Novel Transposon-mediated Approach
Published on: September 11, 2017
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 Evolution - Fast or Slow?
In contrast, regions which code...
Gene Evolution - Fast or Slow?
In contrast, regions which code...
Gene Families
Occasionally these regions can be adapted to take on new roles within the organism, becoming novel genes...
Distribution of Molecular Speeds
Genome Size and the Evolution of New Genes