Lower bounding edit distances between permutations

DOI10.1137/13090897XMaRDI QIDQ2870513zbMATH OpenOpenAlexFDO

Authors Anthony Labarre

Publication date 21 January 2014

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

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

zbMATH Keywords

lower boundsedit distancesymmetric grouptranspositionstheoretical aspects of computational biology

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics in computer science (68R05) Symmetric groups (20B30) General biology and biomathematics (92B05)

Abstract: A number of fields, including the study of genome rearrangements and the design of interconnection networks, deal with the connected problems of sorting permutations in "as few moves as possible", using a given set of allowed operations, or computing the number of moves the sorting process requires, often referred to as the emph{distance} of the permutation. These operations often act on just one or two segments of the permutation, e.g. by reversing one segment or exchanging two segments. The emph{cycle graph} of the permutation to sort is a fundamental tool in the theory of genome rearrangements, and has proved useful in settling the complexity of many variants of the above problems. In this paper, we present an algebraic reinterpretation of the cycle graph of a permutation $pi$ as an even permutation $$, and show how to reformulate our sorting problems in terms of particular factorisations of the latter permutation. Using our framework, we recover known results in a simple and unified way, and obtain a new lower bound on the emph{prefix transposition distance} (where a emph{prefix transposition} displaces the initial segment of a permutation), which is shown to outperform previous results. Moreover, we use our approach to improve the best known lower bound on the emph{prefix transposition diameter} from $2n/3$ to $lfloor3n/4floor$, and investigate a few relations between some statistics on $pi$ and $$.

Recommendations

• A lower bound for the edit-distance problem under an arbitrary cost function
• Edit Distances and Factorisations of Even Permutations
• Lower bounds for edit distance and product metrics via Poincaré-type inequalities
• Almost-optimal sublinear-time edit distance in the low distance regime
• Approximating edit distance in near-linear time
• Approximating edit distance in near-linear time
• scientific article; zbMATH DE number 2079380
• On the computation of edit distance functions
• A sublinear algorithm for weakly approximating edit distance

Cited in

(21)

• Position and content paradigms in genome rearrangements: the wild and crazy world of permutations in genomics
• Move schedules: fast persistence computations in coarse dynamic settings
• Circular permutations and genome shuffling
• Hamiltonian cycles in unitary prefix transposition rearrangement graphs
• Sorting permutations with transpositions in \(O(n^3)\) amortized time
• Edit Distances and Factorisations of Even Permutations
• Distances in graphs of permutations
• scientific article; zbMATH DE number 3857124 (Why is no real title available?)
• An audit tool for genome rearrangement algorithms
• A new upper bound for sorting permutations with prefix transpositions
• CIRCULAR INVERSIONS OF PERMUTATIONS AND THEIR USE IN SORTING PROBLEMS
• On the distance between the expressions of a permutation
• Sorting on graphs by adjacent swaps using permutation groups
• Sorting by prefix block-interchanges
• Plane permutations and applications to a result of Zagier-Stanley and distances of permutations
• Tighter upper bound for sorting permutations with prefix transpositions
• A lower bound on the transposition diameter
• On the edit distance of powers of cycles
• scientific article; zbMATH DE number 7765413 (Why is no real title available?)
• A tight upper bound on the number of cyclically adjacent transpositions to sort a permutation
• Sorting by prefix reversals and prefix transpositions

This page was built for publication: Lower bounding edit distances between permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2870513)