Sorting Strings by Reversals and by Transpositions
From MaRDI portal
Publication:2706200
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
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
