Related Experiment Video
Updated: Jul 3, 2026
04:52
Following the Dynamics of Structural Variants in Experimentally Evolved Populations
Published on: February 3, 2023
Exploring the solution space of sorting by reversals, with experiments and an application to evolution.
Marília D V Braga1, Marie-France Sagot, Celine Scornavacca
1Laboratoire de Biométrie et Biologie Evolutive, UMR 5558, Université de Lyon 1 Claude Bernard, 43, Bd du 11 Novembre 1918, F-69622 Villeurbanne, France. marilia@biomserv.univ-lyon1.fr
Summary
This study introduces a novel algorithm for comparative genomics, efficiently structuring evolutionary rearrangement scenarios. It overcomes limitations of existing methods by classifying and counting optimal solutions, aiding in evolutionary analysis.
Area of Science:
- Computational Biology
- Evolutionary Genomics
- Bioinformatics Algorithms
Background:
- Comparative genomics uses algorithms to sort permutations by reversals for evolutionary scenario reconstruction.
- Current methods provide a single solution, overlooking the vast number of optimal solutions and lacking discrimination criteria.
- Previous work by Bergeron et al. aimed to structure the set of optimal solutions but lacked an efficient computational method.
Purpose of the Study:
- To address the open problem of efficiently computing the structure of optimal solutions in permutation by reversals.
- To develop an algorithm that enumerates classes of solutions and counts solutions within each class.
- To provide a more efficient alternative to complete enumeration for analyzing evolutionary rearrangement scenarios.
Main Methods:
- Development of a novel algorithm to compute the structure of optimal solutions for sorting by reversals.
- The algorithm enumerates all solution classes and quantifies the number of solutions per class.
- Application of the algorithm to analyze rearrangement scenarios in mammalian sex chromosomes.
Main Results:
- The proposed algorithm offers improved theoretical and practical complexity compared to complete enumeration.
- It successfully classifies and counts optimal solutions, providing structure to the solution space.
- Demonstrated reduction in the number of classes using additional constraints.
Conclusions:
- The developed algorithm efficiently addresses the challenge of structuring optimal solutions in comparative genomics.
- It enables more comprehensive analysis of evolutionary rearrangement scenarios, particularly for complex genomes like mammalian sex chromosomes.
- This work provides a significant advancement for evolutionary biology and bioinformatics.
Related Concept Videos
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...
01:41Signal Sequences and Sorting Receptors
Signal sequences are short amino acid sequences that guide newly synthesized proteins to their proper location within the cell. Classical signal sequences are fifteen to sixty amino acids long and present at the N-terminus of a polypeptide chain. Each signal sequence has a conserved segment of basic residues towards their N terminus, a hydrophobic core, and a C-terminus rich in polar residues. The C-terminus also contains a signal cleavage site and features a -3 -1 sequence motif. The -3-1...
01:38Limits to Natural Selection
Organisms that are well-adapted to their environment are more likely to survive and reproduce. However, natural selection does not lead to perfectly adapted organisms. Several factors constrain natural selection.For one, natural selection can only act upon existing genetic variation. Hypothetically, redtusks may enhance elephant survival by deterring ivory-seeking poachers. However, if there are no gene variants—or alleles—for redtusks, natural selection cannot increase the prevalence of...
01:14Reversible and Irreversible Processes
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...
01:10Entropy Change in Reversible Processes
In the Carnot engine, which achieves the maximum efficiency between two reservoirs of fixed temperatures, the total change in entropy is zero. The observation can be generalized by considering any reversible cyclic process consisting of many Carnot cycles. Thus, it can be stated that the total entropy change of any ideal reversible cycle is zero.
The statement can be further generalized to prove that entropy is a state function. Take a cyclic process between any two points on a p-V diagram.
The statement can be further generalized to prove that entropy is a state function. Take a cyclic process between any two points on a p-V diagram.
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...