Related Experiment Videos
An algorithm to enumerate sorting reversals for signed permutations
1Department of Computer Science, University of New Mexico, Albuquerque, NM 87131, USA. acs@soe.ucsc.edu
Summary
This study introduces an efficient algorithm for finding all sorting reversals between genomic permutations, crucial for understanding genome evolution. The new method significantly outperforms existing alternatives in practice for calculating inversion distance.
Area of Science:
- Computational Biology
- Genomics
- Bioinformatics
Background:
- Genome rearrangement distance is estimated by the minimum number of inversions needed to transform gene order.
- This is computed as the reversal distance between signed permutations.
- Sorting by reversals aims to find minimum-length sequences of reversals, but often multiple solutions exist.
Purpose of the Study:
- To address the understudied problem of finding all minimum-length reversal sequences.
- To develop an efficient algorithm for identifying all "sorting reversals."
- To decrease the reversal distance between two permutations.
Main Methods:
- The study derives an efficient algorithm to find all sorting reversals.
- The algorithm's performance is evaluated through experimental results.
- The problem is reduced to finding reversals that decrease the distance between permutations.
Main Results:
- A new algorithm is presented for finding all sorting reversals.
- The algorithm has a time complexity of O(n(3)), similar to brute force.
- Experimental results show dramatic practical performance improvements over existing methods.
Conclusions:
- The developed algorithm efficiently finds all sorting reversals.
- While not asymptotically faster, it offers significant practical advantages.
- This contributes to a better understanding of genome rearrangement and sorting by reversals.