Lower bounding edit distances between permutations

DOI10.1137/13090897XzbMATH Open1286.68366arXiv1201.0365OpenAlexW1964652076MaRDI QIDQ2870513FDOQ2870513

Authors: Anthony Labarre 

Publication date: 21 January 2014

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

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 $$.

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

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

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)

Cited In (21)

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

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)