Sorting by prefix reversals and prefix transpositions

DOI10.1016/j.dam.2014.09.004zbMath1317.68274OpenAlexW2049789525MaRDI QIDQ479021

Ulisses Dias, Zanoni Dias

Publication date: 5 December 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2014.09.004

zbMATH Keywords

approximation algorithmsgenome rearrangementprefix reversalsprefix transpositions

Mathematics Subject Classification ID

Genetics and epigenetics (92D10) Approximation algorithms (68W25) Algorithms on strings (68W32)

Related Items (3)

Approximation algorithms for sorting by length-weighted prefix and suffix operations ⋮ Sorting permutations and binary strings by length-weighted rearrangements ⋮ \(\log\)-lists and their applications to sorting by transpositions, reversals and block-interchanges

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pancake flipping is hard
• Bounding prefix transposition distance for strings and permutations
• An \((18/11)n\) upper bound for sorting by prefix reversals
• Bounds for sorting by prefix reversal
• Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
• Lower Bounding Edit Distances between Permutations
• Sorting by Transpositions Is Difficult
• Sorting Permutations by Reversals and Eulerian Cycle Decompositions
• On the Diameter of the Pancake Network
• Sorting by Transpositions
• Genome Rearrangements and Sorting by Reversals
• Algorithms – ESA 2005

This page was built for publication: Sorting by prefix reversals and prefix transpositions