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

Fast Fourier Transform01:10

Fast Fourier Transform

1.2K
The Fast Fourier Transform (FFT) is a computational algorithm designed to compute the Discrete Fourier Transform (DFT) efficiently. By breaking down the calculations into smaller, manageable sections, the FFT significantly reduces the computational complexity involved. Direct computation of an N-point DFT requires N2 complex multiplications, whereas the FFT algorithm needs only (N/2)log⁡2N multiplications, offering a much faster performance.
The computational efficiency of the FFT becomes...
1.2K
Overview of Transposition and Recombination02:13

Overview of Transposition and Recombination

20.8K
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...
20.8K
Fast Decoupled and DC Powerflow01:24

Fast Decoupled and DC Powerflow

847
The fast decoupled power flow method addresses contingencies in power system operations, such as generator outages or transmission line failures. This method provides quick power flow solutions, essential for real-time system adjustments. Fast decoupled power flow algorithms simplify the Jacobian matrix by neglecting certain elements, leading to two sets of decoupled equations:
847
Transposons01:24

Transposons

3.0K
Transposons, or "jumping genes," are small mobile genetic elements (MGEs) that range from 700 to 40,000 base pairs in length. They are found in all organisms and can move within the same chromosome or transfer to different chromosomes. In some cases, transposons can also jump between different host DNA molecules, such as plasmids or viruses, contributing to genetic variability.Barbara McClintock first discovered these mobile genetic elements in the 1940s while studying maize genetics, and she...
3.0K
Translocation of Proteins into the Mitochondria01:19

Translocation of Proteins into the Mitochondria

13.7K
Mitochondrial precursors are translocated to the internal subcompartments via independent mechanisms involving distinct protein machineries called translocases.
Sorting of outer membrane proteins:
Mitochondrial outer membrane proteins are of two types: the transmembrane, beta-barrel porins, and the membrane-anchored, alpha-helical proteins. Beta-barrel porin precursors are translocated by the TOM complex and inserted into the outer mitochondrial membrane by the SAM complex. In contrast,...
13.7K
Gene Evolution - Fast or Slow?02:05

Gene Evolution - Fast or Slow?

3.8K
3.8K

You might also read

Related Articles

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

Sort by
Same author

A new 1.375-approximation algorithm for sorting by transpositions.

Algorithms for molecular biology : AMB·2022
Same author

Genome Rearrangements on Multigenomic Models: Applications of Graph Convexity Problems.

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

New Genome Similarity Measures based on Conserved Gene Adjacencies.

Journal of computational biology : a journal of computational molecular cell biology·2017
See all related articles

Related Experiment Video

Updated: Apr 3, 2026

RBDT: A Computerized Task System based in Transposition for the Continuous Analysis of Relational Behavior Dynamics in Humans
11:09

RBDT: A Computerized Task System based in Transposition for the Continuous Analysis of Relational Behavior Dynamics in Humans

Published on: July 17, 2021

3.5K

A faster 1.375-approximation algorithm for sorting by transpositions.

Luís Felipe I Cunha1, Luis Antonio B Kowada2, Rodrigo de A Hausen3

  • 11 COPPE - Programa de Engenharia de Sistemas e Computação, Universidade Federal do Rio de Janeiro , Rio de Janeiro, Brazil .

Journal of Computational Biology : a Journal of Computational Molecular Cell Biology
|September 19, 2015
PubMed
Summary

This study addresses the NP-hard problem of sorting by transpositions. We present a corrected 1.375-approximation algorithm with an improved O(n log n) runtime, refining previous methods.

Keywords:
approximation algorithmsgenome rearrangementsorting by transpositions

More Related Videos

High-throughput Parallel Sequencing to Measure Fitness of Leptospira interrogans Transposon Insertion Mutants During Golden Syrian Hamster Infection
11:50

High-throughput Parallel Sequencing to Measure Fitness of Leptospira interrogans Transposon Insertion Mutants During Golden Syrian Hamster Infection

Published on: December 18, 2017

9.4K
Rapid One-step Enzymatic Synthesis and All-aqueous Purification of Trehalose Analogues
09:27

Rapid One-step Enzymatic Synthesis and All-aqueous Purification of Trehalose Analogues

Published on: February 17, 2017

10.9K

Related Experiment Videos

Last Updated: Apr 3, 2026

RBDT: A Computerized Task System based in Transposition for the Continuous Analysis of Relational Behavior Dynamics in Humans
11:09

RBDT: A Computerized Task System based in Transposition for the Continuous Analysis of Relational Behavior Dynamics in Humans

Published on: July 17, 2021

3.5K
High-throughput Parallel Sequencing to Measure Fitness of Leptospira interrogans Transposon Insertion Mutants During Golden Syrian Hamster Infection
11:50

High-throughput Parallel Sequencing to Measure Fitness of Leptospira interrogans Transposon Insertion Mutants During Golden Syrian Hamster Infection

Published on: December 18, 2017

9.4K
Rapid One-step Enzymatic Synthesis and All-aqueous Purification of Trehalose Analogues
09:27

Rapid One-step Enzymatic Synthesis and All-aqueous Purification of Trehalose Analogues

Published on: February 17, 2017

10.9K

Area of Science:

  • Computational complexity
  • Algorithm analysis
  • Combinatorial optimization

Background:

  • Sorting by transpositions is an NP-hard problem.
  • Previous approximation algorithms exist, including 1.5- and 1.375-approximation ratios.
  • The permutation tree data structure has been used to improve runtime.

Purpose of the Study:

  • To evaluate the correctness of Firoz et al.'s (2011) claimed O(n log n) sorting by transpositions algorithm.
  • To propose a new, efficient, and correct approximation algorithm for sorting by transpositions.

Main Methods:

  • We provide counter-examples to invalidate Firoz et al.'s strategy.
  • We adapt Elias and Hartman's (2006) 1.375-approximation algorithm.
  • The permutation tree data structure is integrated to optimize runtime.

Main Results:

  • Firoz et al.'s (2011) strategy for improving sorting by transpositions runtime is shown to be incorrect.
  • A novel 1.375-approximation algorithm for sorting by transpositions is developed.
  • The new algorithm achieves an optimal O(n log n) runtime.

Conclusions:

  • The permutation tree method, as applied by Firoz et al., does not guarantee correctness.
  • A provably correct and efficient O(n log n) 1.375-approximation algorithm for sorting by transpositions is presented.