Approximation algorithms for sorting by length-weighted prefix and suffix operations

DOI10.1016/j.tcs.2015.05.039zbMath1330.68116OpenAlexW604810461MaRDI QIDQ500990

Zanoni Dias, Guillaume Fertin, Carla Negri Lintzmayer

Publication date: 8 October 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.05.039

zbMATH Keywords

approximation algorithmsgenome rearrangementslength-weighted operationsprefix and suffix operationsreversals and transpositions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Genetics and epigenetics (92D10) Approximation algorithms (68W25)

Related Items

Prefix and suffix reversals on strings, Sorting permutations and binary strings by length-weighted rearrangements, Length-weighted \(\lambda\)-rearrangement distance

Cites Work

• Unnamed Item
• Unnamed Item
• Sorting by prefix reversals and prefix transpositions
• Pancake flipping is hard
• Improved bounds on sorting by length-weighted reversals
• An approximation algorithm for sorting by reversals and transpositions
• Bounds for sorting by prefix reversal
• A 2-approximation algorithm for genome rearrangements by reversals and transpositions
• On the problem of sorting burnt pancakes
• On sorting unsigned permutations by double-cut-and-joins
• Algorithms for computational biology. First international conference, AlCoB 2014, Tarragona, Spain, July 1--3, 2014. Proceedings
• Sorting by Transpositions Is Difficult
• Transforming cabbage into turnip
• Sorting Permutations by Reversals and Eulerian Cycle Decompositions
• Sorting by Transpositions
• Combinatorial Pattern Matching
• Sorting Permutations by Prefix and Suffix Versions of Reversals and Transpositions
• Algorithms – ESA 2005
• Signed genome rearrangement by reversals and transpositions: Models and approximations