An approximation algorithm for sorting by reversals and transpositions
DOI10.1016/J.JDA.2007.09.002zbMATH Open1186.92035OpenAlexW2163195596MaRDI QIDQ1018097FDOQ1018097
Authors: Atif Rahman, Swakkhar Shatabda, Masud Hasan 
Publication date: 13 May 2009
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2007.09.002
Recommendations
approximation algorithmgenome rearrangementbreakpoints in a permutationcycle decomposition graphmaximum cycle decompositionsorting by reversals and transpositions
Applications of graph theory (05C90) Biochemistry, molecular biology (92C40) Problems related to evolution (92D15) Graph algorithms (graph-theoretic aspects) (05C85) Computational methods for problems pertaining to biology (92-08)
Cites Work
- Sorting a bridge hand
- Sorting by Transpositions
- Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement
- A 2-approximation algorithm for genome rearrangements by reversals and transpositions
- A simpler 1.5-approximation algorithm for sorting by transpositions
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Genome Rearrangements and Sorting by Reversals
- \((1+\varepsilon)\)-approximation of sorting by reversals and transpositions.
- Title not available (Why is that?)
- Improved approximation for breakpoint graph decomposition and sorting by reversals
- A further improved approximation algorithm for breakpoint graph decomposition
Cited In (37)
- A 2.25-Approximation Algorithm for Cut-and-Paste Sorting of Unsigned Circular Permutations
- \((1+\varepsilon)\)-approximation of sorting by reversals and transpositions.
- Working on the problem of sorting by transpositions on genome rearrangements
- Advances on sorting by reversals
- Implementation of bubble sort and the odd-even transposition sort on a rack of transputers
- Sorting permutations and binary strings by length-weighted rearrangements
- (1+ε)-Approximation of Sorting by Reversals and Transpositions
- Sorting of Permutations by Cost-Constrained Transpositions
- Average-case analysis of perfect sorting by reversals
- A simpler and faster 1.5-approximation algorithm for sorting by transpositions
- Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement
- Title not available (Why is that?)
- Length-weighted \(\lambda\)-rearrangement distance
- A new approximation algorithm for cut-and-paste sorting of unsigned circular permutations
- An audit tool for genome rearrangement algorithms
- A \((1.408+\varepsilon )\)-approximation algorithm for sorting unsigned genomes by reciprocal translocations
- Improving the algorithm of Bafna and Pevzner for the problem of sorting by transpositions: a practical approach
- Signed genome rearrangement by reversals and transpositions: Models and approximations
- Approximation algorithms for sorting permutations by fragmentation-weighted operations
- Heuristics for the sorting signed permutations by reversals and transpositions problem
- An approximation algorithm for genome sorting by reversals to recover all adjacencies
- Replacement sort revisited: The ``gold standard unearthed!
- A factor-\((1.408+\varepsilon)\) approximation for sorting unsigned genomes by reciprocal translocations
- A new approximation algorithm for sorting of signed permutations
- A New and Faster Method of Sorting by Transpositions
- Algorithms – ESA 2005
- Spin-the-bottle sort and annealing sort: oblivious sorting via round-robin random comparisons
- A simpler 1.5-approximation algorithm for sorting by transpositions
- A randomized FPT approximation algorithm for maximum alternating-cycle decomposition with applications
- Genome Rearrangement Algorithms for Unsigned Permutations with O(logn) Singletons
- Approximation algorithms for sorting by \(k\)-cuts on signed permutations
- Approximation algorithms for sorting permutations by length-weighted short rearrangements
- Pancake flipping and sorting permutations
- A further improved approximation algorithm for breakpoint graph decomposition
- Approximation algorithms for sorting by length-weighted prefix and suffix operations
- Sorting permutations by prefix and suffix versions of reversals and transpositions
- Title not available (Why is that?)
This page was built for publication: An approximation algorithm for sorting by reversals and transpositions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1018097)
