Related Experiment Videos
A lower bound on the reversal and transposition diameter.
João Meidanis1, Maria M T Walter, Zanoni Dias
1Universidade de Campinas, Instituto de Computação, 13083-971 Campinas, São Paulo, Brazil.
Summary
Genome evolution can be studied using gene permutations and rearrangement operations like reversals and transpositions. This study determines the distance for a specific signed permutation, finding it to be floor n/2 + 2 for n>=3.
Area of Science:
- Computational Biology
- Genomics
- Bioinformatics
Background:
- Genomes can be modeled as permutations of genes.
- Genome evolution is studied by analyzing the distance between these permutations based on rearrangement operations.
- Reversals and transpositions are key operations in understanding genome rearrangements.
Purpose of the Study:
- To determine the reversal and transposition distance for a specific signed permutation, pi(n) = (-1 -2 ... -(n-1) -n).
- To investigate the relationship between this distance and the diameter of the permutation group under these operations.
Main Methods:
- Representing genomes as signed permutations.
- Applying reversal and transposition operations to permutations.
- Calculating the minimum number of operations to transform a given permutation to the identity permutation.
Main Results:
- The reversal and transposition distance for the signed permutation pi(n) = (-1 -2 ... -(n-1) -n) with respect to the identity was found to be floor n/2 + 2 for all n >= 3.
- This value is conjectured to represent the diameter of the permutation group under these operations.
Conclusions:
- The calculated distance provides a specific metric for genome evolution analysis.
- The conjecture suggests a fundamental property of the permutation group concerning reversals and transpositions.