Approximating reversal distance for strings with bounded number of duplicates

DOI10.1016/j.dam.2006.05.011zbMath1108.68127OpenAlexW2056412902MaRDI QIDQ868388

Petr Kolman, Tomasz Walen

Publication date: 2 March 2007

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

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

zbMATH Keywords

approximation algorithmsminimum common string partitionedit distancestring comparisonsorting by reversals

Mathematics Subject Classification ID

Searching and sorting (68P10) Approximation algorithms (68W25)

Related Items (8)

Heuristics for Reversal Distance Between Genomes with Duplicated Genes ⋮ A NOTE ON COMPLEXITY OF GENETIC MUTATIONS ⋮ An approximation algorithm for genome sorting by reversals to recover all adjacencies ⋮ Minimum common string partition revisited ⋮ Solving the maximum duo-preservation string mapping problem with linear programming ⋮ A \((1.4+\epsilon)\)-approximation algorithm for the 2-\textsc{Max-Duo} problem ⋮ Unnamed Item ⋮ A (1.4 + epsilon)-Approximation Algorithm for the 2-Max-Duo Problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reconstructing an ancestral genome using minimum segments duplications and reversals.
• Sorting Strings by Reversals and by Transpositions
• The greedy algorithm for the minimum common string partition problem
• Transforming cabbage into turnip
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• Combinatorial Pattern Matching
• Mathematical Foundations of Computer Science 2005
• Algorithms and Computation

This page was built for publication: Approximating reversal distance for strings with bounded number of duplicates