Sorting by Transpositions
From MaRDI portal
Publication:4388990
DOI10.1137/S089548019528280XzbMath0973.92014OpenAlexW2023749136MaRDI QIDQ4388990
Vineet Bafna, Pavel A. Pevzner
Publication date: 11 May 1998
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s089548019528280x
approximation algorithmsymmetric grouptranspositionscomputational molecular biologygenome rearrangements
Searching and sorting (68P10) Permutations, words, matrices (05A05) Biochemistry, molecular biology (92C40) Computational methods for problems pertaining to biology (92-08)
Related Items (85)
Reconstructing an ancestral genome using minimum segments duplications and reversals. ⋮ A topological framework for signed permutations ⋮ The complexity of genome rearrangement combinatorics under the infinite sites model ⋮ A 3.5-Approximation Algorithm for Sorting by Intergenic Transpositions ⋮ Sorting by multi-cut rearrangements ⋮ APPROXIMATE BLOCK SORTING ⋮ Position and content paradigms in genome rearrangements: the wild and crazy world of permutations in genomics ⋮ Signed Hultman numbers and signed generalized commuting probability in finite groups ⋮ Approximation algorithms for sorting by bounded singleton moves ⋮ Finding similar/diverse solutions in answer set programming ⋮ Exploiting pseudo-locality of interchange distance ⋮ Optimal algorithms for uncovering synteny problem ⋮ Exemplar or matching: modeling DCJ problems with unequal content genome data ⋮ Sorting by \(k\)-cuts on signed permutations ⋮ A new approach for the reversal distance with indels and moves in intergenic regions ⋮ Structural properties and tractability results for linear synteny ⋮ Improved upper bound for sorting permutations by prefix transpositions ⋮ A versatile combinatorial approach of studying products of long cycles in symmetric groups ⋮ Computing similarity distances between rankings ⋮ An 5/4-Approximation Algorithm for Sorting Permutations by Short Block Moves ⋮ Permutation patterns in genome rearrangement problems: the reversal model ⋮ Block Sorting Is APX-Hard ⋮ Sorting by prefix block-interchanges ⋮ Rearrangement events on circular genomes ⋮ Sorting permutations: Games, genomes, and cycles ⋮ A new approximation algorithm for sorting of signed permutations ⋮ Approximate String Matching with Address Bit Errors ⋮ An efficient algorithm for one-sided block ordering problem under block-interchange distance ⋮ An approximation algorithm for genome sorting by reversals to recover all adjacencies ⋮ A 2.25-Approximation Algorithm for Cut-and-Paste Sorting of Unsigned Circular Permutations ⋮ Exact Markov chain-based runtime analysis of a discrete particle swarm optimization algorithm on sorting and OneMax ⋮ Block crossings in one-sided tanglegrams ⋮ The transposition median problem is NP-complete ⋮ A new approximation algorithm for cut-and-paste sorting of unsigned circular permutations ⋮ A \((1+\varepsilon)\)-approximation algorithm for sorting by short block-moves ⋮ Girth of pancake graphs ⋮ Unnamed Item ⋮ Pattern matching with address errors: rearrangement distances ⋮ Edit Distances and Factorisations of Even Permutations ⋮ Block Sorting is Hard ⋮ Multi-break rearrangements and chromosomal evolution ⋮ Sorting by prefix reversals and prefix transpositions ⋮ Sorting permutations with transpositions in \(O(n^3)\) amortized time ⋮ Edit distance with move operations ⋮ Edit distance with block deletions ⋮ Hamiltonian cycles in unitary prefix transposition rearrangement graphs ⋮ Pancake flipping and sorting permutations ⋮ Approximation algorithms for sorting permutations by extreme block-interchanges ⋮ CIRCULAR INVERSIONS OF PERMUTATIONS AND THEIR USE IN SORTING PROBLEMS ⋮ Tighter upper bound for sorting permutations with prefix transpositions ⋮ COMPUTING SIGNED PERMUTATIONS OF POLYGONS ⋮ Approximation algorithms for sorting by length-weighted prefix and suffix operations ⋮ Expected number of breakpoints after \(t\) random reversals in genomes with duplicate genes ⋮ Sorting by Transpositions Is Difficult ⋮ Transposition Rearrangement: Linear Algorithm for Length-Cost Model ⋮ Diameter bounds and recursive properties of Full-Flag Johnson graphs ⋮ Uniquely pressable graphs: characterization, enumeration, and recognition ⋮ A 14/11-approximation algorithm for sorting by short block-moves ⋮ On maximal instances for the original syntenic distance ⋮ Approximate string matching with stuck address bits ⋮ A simpler and faster 1.5-approximation algorithm for sorting by transpositions ⋮ Signed genome rearrangement by reversals and transpositions: Models and approximations ⋮ On sorting by 3-bounded transpositions ⋮ An improved algorithm for sorting by block-interchanges based on permutation groups ⋮ On the effective and automatic enumeration of polynomial permutation classes ⋮ Interchange rearrangement: the element-cost model ⋮ Efficient computations of \(\ell _1\) and \(\ell _{\infty }\) rearrangement distances ⋮ A quadratic time 2-approximation algorithm for block sorting ⋮ On the computational complexity of closest genome problems ⋮ An approximation algorithm for sorting by reversals and transpositions ⋮ Finding All Sorting Tandem Duplication Random Loss Operations ⋮ Reversal and transposition medians ⋮ Reversals distance considering flexible intergenic regions sizes ⋮ An Audit Tool for Genome Rearrangement Algorithms ⋮ Bounding prefix transposition distance for strings and permutations ⋮ Sorting by bounded block-moves ⋮ Hultman Numbers and Generalized Commuting Probability in Finite Groups ⋮ Approximate string matching with address bit errors ⋮ The Emperor Has No Caps! A Comparison of DCJ and Algebraic Distances ⋮ The role of colour flows in matrix element computations and Monte Carlo simulations ⋮ Improving the algorithm of Bafna and Pevzner for the problem of sorting by transpositions: a practical approach ⋮ A new upper bound for sorting permutations with prefix transpositions ⋮ \((1+\varepsilon)\)-approximation of sorting by reversals and transpositions. ⋮ Approximation algorithms for sorting by \(k\)-cuts on signed permutations ⋮ On Sorting by 3-Bounded Transpositions
This page was built for publication: Sorting by Transpositions
