Sorting by Transpositions Is Difficult

DOI10.1007/978-3-642-22006-7_55zbMath1334.68085arXiv1011.1157OpenAlexW1890701999MaRDI QIDQ3012840

Irena Rusu, Laurent Bulteau, Guillaume Fertin

Publication date: 6 July 2011

Published in: SIAM Journal on Discrete Mathematics, Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1011.1157

zbMATH Keywords

computational complexity NP-hard comparative genomics sorting permutations evolutionary distance transposition distance theoretical aspects of computational biology sorting by transpositions problem

Mathematics Subject Classification ID

Searching and sorting (68P10) Problems related to evolution (92D15) Combinatorics in computer science (68R05) Permutations, words, matrices (05A05) Biochemistry, molecular biology (92C40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Genetics and epigenetics (92D10)

Related Items

A topological framework for signed permutations ⋮ A 3.5-Approximation Algorithm for Sorting by Intergenic Transpositions ⋮ Tandem Duplications, Segmental Duplications and Deletions, and Their Applications ⋮ Sorting by multi-cut rearrangements ⋮ Approximation algorithms for sorting permutations by length-weighted short rearrangements ⋮ Sorting on graphs by adjacent swaps using permutation groups ⋮ Approximation algorithms for sorting by bounded singleton moves ⋮ Permutation-constrained common string partitions with applications ⋮ Sorting by \(k\)-cuts on signed permutations ⋮ Improved upper bound for sorting permutations by prefix transpositions ⋮ Sorting by Cuts, Joins and Whole Chromosome Duplications ⋮ An 5/4-Approximation Algorithm for Sorting Permutations by Short Block Moves ⋮ Block Sorting Is APX-Hard ⋮ A 1.375-approximation algorithm for unsigned translocation sorting ⋮ Sorting by prefix block-interchanges ⋮ An efficient algorithm for one-sided block ordering problem under block-interchange distance ⋮ Block Crossings in Storyline Visualizations ⋮ Block crossings in one-sided tanglegrams ⋮ A new approximation algorithm for cut-and-paste sorting of unsigned circular permutations ⋮ A \((1+\varepsilon)\)-approximation algorithm for sorting by short block-moves ⋮ Unnamed Item ⋮ Sorting by prefix reversals and prefix transpositions ⋮ Sorting permutations with transpositions in \(O(n^3)\) amortized time ⋮ Hamiltonian cycles in unitary prefix transposition rearrangement graphs ⋮ CIRCULAR INVERSIONS OF PERMUTATIONS AND THEIR USE IN SORTING PROBLEMS ⋮ Tighter upper bound for sorting permutations with prefix transpositions ⋮ Approximation algorithms for sorting by length-weighted prefix and suffix operations ⋮ Sorting by Transpositions Is Difficult ⋮ Sorting permutations and binary strings by length-weighted rearrangements ⋮ On the hardness of maximum rank aggregation problems ⋮ Length-weighted \(\lambda\)-rearrangement distance ⋮ On the computational complexity of closest genome problems ⋮ Plane Permutations and Applications to a Result of Zagier--Stanley and Distances of Permutations ⋮ An Audit Tool for Genome Rearrangement Algorithms ⋮ Bounding prefix transposition distance for strings and permutations ⋮ Rearrangements in Phylogenetic Inference: Compare, Model, or Encode? ⋮ A Retrospective on Genomic Preprocessing for Comparative Genomics ⋮ A new upper bound for sorting permutations with prefix transpositions ⋮ Approximation algorithms for sorting by \(k\)-cuts on signed permutations ⋮ Computing the Tandem Duplication Distance is NP-Hard

Cites Work