A simpler and faster 1.5-approximation algorithm for sorting by transpositions

DOI10.1016/j.ic.2005.09.002zbMath1092.68580MaRDI QIDQ2490115

Ron Shamir, Tzvika Hartman

Publication date: 28 April 2006

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2005.09.002

zbMATH Keywords

Computational biology; Genome rearrangements; Sorting permutations by transpositions

Mathematics Subject Classification ID

68P10: Searching and sorting

Related Items

The transposition median problem is NP-complete, Bounding prefix transposition distance for strings and permutations, Sorting by Transpositions Is Difficult

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A 2-approximation algorithm for genome rearrangements by reversals and transpositions
• Transforming cabbage into turnip
• A Simpler 1.5-Approximation Algorithm for Sorting by Transpositions
• Efficient Data Structures and a New Randomized Approach for Sorting Signed Permutations by Reversals
• Working on the Problem of Sorting by Transpositions on Genome Rearrangements
• Self-adjusting binary search trees
• Sorting Permutations by Reversals and Eulerian Cycle Decompositions
• Sorting by Transpositions
• Genome Rearrangements and Sorting by Reversals
• A Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals
• Signed genome rearrangement by reversals and transpositions: Models and approximations
• Sorting a bridge hand