Related Experiment Video
Updated: Jan 24, 2026
07:41
A Method for Measuring Metabolism in Sorted Subpopulations of Complex Cell Communities Using Stable Isotope Tracing
Published on: February 4, 2017
8.9K
On the Complexity of Sorting by Reversals and Transpositions Problems
Andre Rodrigues Oliveira1, Klairton Lima Brito1, Ulisses Dias2
1Institute of Computing, University of Campinas, Campinas, Brazil.
Summary
The computational complexity of sorting by reversals and transpositions in comparative genomics is NP-hard. This study proves the problem
Area of Science:
- Comparative genomics
- Computational biology
- Bioinformatics
Background:
- Genomic rearrangements like reversals and transpositions are key mutations studied in comparative genomics.
- The reversal and transposition distance quantifies genome evolution but its computational complexity remained an open problem for over two decades.
Purpose of the Study:
- To determine the computational complexity of the sorting by reversals and transpositions problem.
- To analyze the complexity of generalized versions of this problem with weighted operations.
Main Methods:
- The study employs theoretical computer science approaches to analyze the computational complexity.
- Proof techniques are used to establish the NP-hard nature of the problem.
Main Results:
- The paper proves that computing the reversal and transposition distance is NP-hard for both signed and unsigned permutations.
- A generalization involving weighted operations (weights ≤ 1.5) is also proven to be NP-hard.
Conclusions:
- The sorting by reversals and transpositions problem is computationally intractable.
- These findings have significant implications for understanding genome evolution and developing efficient algorithms.
Related Concept Videos
02:13Overview of Transposition and Recombination
19.1K
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...
19.1K
01:14Diode: Reverse bias
1.9K
A diode is reverse-biased when the positive terminal of an external voltage source is connected to the n-type material and the negative terminal to the p-type material. This configuration opposes the natural direction of current flow through the diode, effectively increasing the width of the depletion region and the barrier potential. The reverse bias condition produces a minimal leakage current, primarily due to minority charge carriers. This leakage becomes significant when the reverse...
1.9K
01:14Reversible and Irreversible Processes
5.6K
The thermodynamic processes can be classified into reversible and irreversible processes. The processes that can be restored to their initial state are called reversible processes. It is only possible if the process is in quasi-static equilibrium, i.e., it takes place in infinitesimally small steps, and the system remains at equilibrium However, these are ideal processes and do not occur naturally. An ideal system undergoing a reversible process is always in thermodynamic equilibrium within...
5.6K
01:34Nuclear Protein Sorting
6.2K
Nuclear protein sorting is the selective trafficking of histones, polymerases, gene regulatory proteins into the nucleus and exporting RNAs and ribosomes to the cytosol. It is a tightly controlled process that regulates gene expression within a cell.
Proteins targeted to the nucleus carry nuclear localization signals or NLS recognized by import receptors in the cytosol. Similarly, proteins with nuclear export signals are recognized by export receptors. Import and export receptors are...
Proteins targeted to the nucleus carry nuclear localization signals or NLS recognized by import receptors in the cytosol. Similarly, proteins with nuclear export signals are recognized by export receptors. Import and export receptors are...
6.2K
01:39Mitochondrial Protein Sorting
5.7K
Mitochondria are double-membrane organelles of the eukaryotes involved in cellular metabolism, signaling, ATP synthesis, and programmed cell death. Each of these processes requires specific proteins and enzymes that must be correctly sorted to the right mitochondrial subcompartment for the proper functioning of the organelle.
Most of these mitochondrial proteins are encoded by the nucleus and imported to the mitochondria as unfolded or loosely folded precursors. Mitochondrial precursors...
Most of these mitochondrial proteins are encoded by the nucleus and imported to the mitochondria as unfolded or loosely folded precursors. Mitochondrial precursors...
5.7K
02:41Protein Complex Assembly
16.7K
Proteins can form homomeric complexes with another unit of the same protein or heteromeric complexes with different types. Most protein complexes self-assemble spontaneously via ordered pathways, while some proteins need assembly factors that guide their proper assembly. Despite the crowded intracellular environment, proteins usually interact with their correct partners and form functional complexes.
Many viruses self-assemble into a fully functional unit using the infected host cell to...
Many viruses self-assemble into a fully functional unit using the infected host cell to...
16.7K