An approximation algorithm for sorting by reversals and transpositions

DOI10.1016/j.jda.2007.09.002zbMath1186.92035OpenAlexW2163195596MaRDI QIDQ1018097

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

zbMATH Keywords

approximation algorithmgenome rearrangementbreakpoints in a permutationcycle decomposition graphmaximum cycle decompositionsorting by reversals and transpositions

Mathematics Subject Classification ID

Problems related to evolution (92D15) Applications of graph theory (05C90) Biochemistry, molecular biology (92C40) Graph algorithms (graph-theoretic aspects) (05C85) Computational methods for problems pertaining to biology (92-08)

Related Items

Approximation algorithms for sorting permutations by length-weighted short rearrangements ⋮ A 2.25-Approximation Algorithm for Cut-and-Paste Sorting of Unsigned Circular Permutations ⋮ A new approximation algorithm for cut-and-paste sorting of unsigned circular permutations ⋮ Pancake flipping and sorting permutations ⋮ Approximation algorithms for sorting by length-weighted prefix and suffix operations ⋮ Sorting permutations and binary strings by length-weighted rearrangements ⋮ Length-weighted \(\lambda\)-rearrangement distance ⋮ An Audit Tool for Genome Rearrangement Algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A 2-approximation algorithm for genome rearrangements by reversals and transpositions
• Improved approximation for breakpoint graph decomposition and sorting by reversals
• A further improved approximation algorithm for breakpoint graph decomposition
• \((1+\varepsilon)\)-approximation of sorting by reversals and transpositions.
• Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement
• A Simpler 1.5-Approximation Algorithm for Sorting by Transpositions
• Sorting by Transpositions
• Genome Rearrangements and Sorting by Reversals
• Sorting a bridge hand

This page was built for publication: An approximation algorithm for sorting by reversals and transpositions