Related Experiment Video
Updated: Jul 19, 2026
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
New bounds and tractable instances for the transposition distance
1Département de Mathématique, Université Libre de Bruxelles, Service de Géométrie, Combinatoire et Théorie des Groupes, Bruxelles, Belgium. alabarre@ulb.ac.be
IEEE/ACM Transactions on Computational Biology and Bioinformatics
|November 7, 2006
Summary
This study introduces new methods to calculate the sorting by transpositions distance for permutations. Researchers established novel graph connections to efficiently compute this distance for new permutation classes.
Area of Science:
- Combinatorics
- Computer Science
- Algorithm Analysis
Background:
- The sorting by transpositions problem seeks the shortest sequence of adjacent interval exchanges to sort a permutation.
- The computational complexity of finding this optimal sequence and its length (transposition distance) remains an open problem since its introduction in 1995.
Purpose of the Study:
- To develop efficient methods for computing the transposition distance.
- To establish new theoretical bounds for permutation sorting.
- To explore connections between different permutation representations.
Main Methods:
- Establishing novel connections between two distinct graph representations of permutations.
- Developing algorithms to compute transposition distance in linear time and space for specific permutation classes.
- Proving a new tight upper bound on the transposition distance by demonstrating that all permutations can be derived from these classes.
Main Results:
- Computed the transposition distance for several non-trivial permutation classes efficiently, bypassing complex graph structures.
- Established a new tight upper bound on the transposition distance.
- Provided improved bounds and exact formulas for the transposition distance of other permutation families.
Conclusions:
- The study offers significant advancements in understanding and computing the transposition distance.
- The developed methods provide polynomial-time solutions for previously intractable problems.
- This research opens new avenues for analyzing permutation sorting algorithms.
More Related Videos
11:36Creation of a Dense Transposon Insertion Library Using Bacterial Conjugation in Enterobacterial Strains Such As Escherichia Coli or Shigella flexneri
Published on: September 23, 2017
04:04Real-Time Quantification of the Effects of IS200/IS605 Family-Associated TnpB on Transposon Activity
Published on: January 20, 2023
Related Concept Videos
02:13Overview 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...
01:24Transposons
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...
01:29Distance Problem
When an object's velocity changes over time, the total distance traveled can be determined by summing small displacement intervals over short increments. This approach approximates the true distance through numerical summation and the use of integral calculus. An estimate of the total displacement can be obtained by measuring velocity at regular intervals and multiplying each value by the corresponding time step.If a runner accelerates over the first three seconds of a race, speed measurements...
01:27Extended Versions of Green’s Theorem
Green’s Theorem connects the circulation of a vector field around a closed curve with the behavior of the field across the region enclosed by that curve. It provides a way to replace a line integral around a boundary with a double integral over the interior region, making it especially useful in plane geometry, fluid flow, and vector calculus.Although Green’s Theorem is often introduced using simple regions without gaps, it can also be applied to regions made from several simple parts. This...
02:57DNA-only Transposons
DNA-only transposons are called autonomous transposons since they code for the enzyme transposase that is required for the transposition mechanism. Insertion of transposons can alter gene functions in multiple ways. They can mutate the gene, alter gene expression by introducing a novel promoter or insulator sequence, introduce new splice sites, and change the mRNA transcripts produced, or remodel chromatin structure.
The donor site from where the transposon is excised is either degraded or...
The donor site from where the transposon is excised is either degraded or...
01:26Vector Forms of Green’s Theorem
The study of fluid motion often involves understanding how local rotational behavior relates to global circulation. In the context of a pond with pollutants, direct measurement of water movement along an irregular shoreline can be impractical. Green’s Theorem in vector form provides an alternative by relating the circulation around a closed boundary to properties of the flow within the enclosed region.Measurements of water velocity at different points define a continuous vector field that...