Related Experiment Video
Updated: May 29, 2026
09:40
Novel Sequence Discovery by Subtractive Genomics
Published on: January 25, 2019
Listing all parsimonious reversal sequences: new algorithms and perspectives
Ghada Badr1, Krister M Swenson, David Sankoff
1SITE (School of Information Technology and Engineering), University of Ottawa, Ottawa, Canada. badrghada@hotmail.com
Summary
This study addresses the All Sorting Sequences by Reversals (ASSR) problem in comparative genomics. It offers a new framework to theoretically compare algorithms and empirically speed up solutions for gene order analysis.
Area of Science:
- Computational Biology
- Genomics
- Bioinformatics
Background:
- The sorting by reversals problem is central to comparative genomics, seeking minimum reversal sequences between genomes.
- The All Sorting Sequences by Reversals (ASSR) problem is crucial due to multiple minimum solutions.
Purpose of the Study:
- To revisit and provide a unified framework for the ASSR problem in uni-chromosomal genomes without duplications.
- To enable theoretical comparison of running times for existing ASSR algorithms.
- To propose an improved framework for empirical speedup of ASSR algorithms.
Main Methods:
- Analysis of the fundamental framework underlying current ASSR algorithms.
- Theoretical comparison of algorithm running times based on the unified framework.
- Development and empirical testing of an improved algorithmic framework.
Main Results:
- A unified perspective on the ASSR problem, facilitating theoretical performance comparisons.
- An empirically validated framework that enhances the speed of existing ASSR algorithms.
- New insights into the computational complexity and solutions for gene order rearrangements.
Conclusions:
- The proposed framework offers a significant advancement in addressing the ASSR problem.
- This work provides tools for more efficient comparative genomic analyses.
- The study contributes to understanding genome evolution through sequence rearrangement analysis.
Related Concept Videos
01:05Maxam-Gilbert Sequencing
In the same year as the discovery of the Sanger sequencing method, another group of scientists, Allan Maxam and Walter Gilbert, demonstrated their chemical-cleavage method for DNA sequencing. The Maxam-Gilbert method relies on using different chemicals that can cleave the DNA sequence at specific sites, the separation of resulting DNA fragments of variable size using electrophoresis, and deciphering the DNA sequence from the resulting gel bands.
Challenges of the Maxam-Gilbert Method
The...
Challenges of the Maxam-Gilbert Method
The...
01:34Woodward–Hoffmann Selection Rules and Microscopic Reversibility
Electrocyclic reactions, cycloadditions, and sigmatropic rearrangements are concerted pericyclic reactions that proceed via a cyclic transition state. These reactions are stereospecific and regioselective. The stereochemistry of the products depends on the symmetry characteristics of the interacting orbitals and the reaction conditions. Accordingly, pericyclic reactions are classified as either symmetry-allowed or symmetry-forbidden. Woodward and Hoffmann presented the selection criteria for...
02:51Multi-species Conserved Sequences
Next-generation sequencing technologies have created large genomic databases of a variety of animals and plants. Ever since the human genome project was completed, scientists studied the genome of primates, mammals, and other phylogenetically distant living beings. Such large-scale studies have provided new insights into the evolutionary relationship between organisms.
Although the genome of each species varies greatly from each other, a few sequences are highly conserved. Such conserved DNA...
Although the genome of each species varies greatly from each other, a few sequences are highly conserved. Such conserved DNA...
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...
03:00Next-generation Sequencing
The first human genome sequencing project cost $2.7 billion and was declared complete in 2003, after 15 years of international cooperation and collaboration between several research teams and funding agencies. Today, with the advent of next-generation sequencing technologies, the cost and time of sequencing a human genome have dropped over 100 fold.
Next-Generation Sequencing Methods
Although all next-generation methods use different technologies, they all share a set of standard features.
Next-Generation Sequencing Methods
Although all next-generation methods use different technologies, they all share a set of standard features.
02:53Conservative Site-specific Recombination and Phase Variation
Because the DNA segments are cut and reorganized in a direction-specific manner, site-specific recombination has emerged as an efficient genetic engineering technique. Flippase and Cyclization recombinases or Flp and Cre, respectively, are two members of the tyrosine recombinase family derived from bacteriophages, that are used to mediate site-specific DNA insertions, deletions, and targeted expression of proteins in mammalian cell lines.
The recognition sites for Cre recombinase called LoxP...
The recognition sites for Cre recombinase called LoxP...