Sorting Strings by Reversals and by Transpositions

DOI10.1137/S0895480197331995zbMath0968.68116OpenAlexW2011472686MaRDI QIDQ2706200

David A. Christie, Robert W. Irving

Publication date: 19 March 2001

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480197331995

zbMATH Keywords

sortingNP-complete problemsstringstranspositionsreversalsgenome comparison

Mathematics Subject Classification ID

Problems related to evolution (92D15) Combinatorics in computer science (68R05) Combinatorics on words (68R15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (20)

Heuristics for Reversal Distance Between Genomes with Duplicated Genes ⋮ A NOTE ON COMPLEXITY OF GENETIC MUTATIONS ⋮ APPROXIMATE BLOCK SORTING ⋮ (Prefix) reversal distance for (signed) strings with few blocks or small alphabets ⋮ Permutation-constrained common string partitions with applications ⋮ Prefix and suffix reversals on strings ⋮ A new approach for the reversal distance with indels and moves in intergenic regions ⋮ Approximating reversal distance for strings with bounded number of duplicates ⋮ Prefix and Suffix Reversals on Strings ⋮ An approximation algorithm for genome sorting by reversals to recover all adjacencies ⋮ Minimum common string partition revisited ⋮ Multiple genome rearrangement by swaps and by element duplications ⋮ Prefix and suffix transreversals on binary and ternary strings ⋮ Quick Greedy Computation for Minimum Common String Partitions ⋮ Sorting by Transpositions Is Difficult ⋮ Quick greedy computation for minimum common string partition ⋮ Bounding prefix transposition distance for strings and permutations ⋮ Kernelization of Whitney Switches ⋮ Kernelization of Whitney Switches ⋮ The complexity of string partitioning

This page was built for publication: Sorting Strings by Reversals and by Transpositions