NDLI: Lower Bounding Edit Distances between Permutations

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Labarre, Anthony
Copyright Year	2013
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 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 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 $\overline{\pi}$ and show how to reformulate our sorting problems in terms of particular factorizations 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 prefix transposition distance (where a 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 prefix transposition diameter from $2n/3$ to $\lfloor 3n/4\rfloor$ and investigate a few relations between some statistics on $\pi$ and $\overline{\pi}$.
Starting Page	1410
Ending Page	1428
Page Count	19
File Format	PDF
ISSN	08954801
DOI	10.1137/13090897X
e-ISSN	10957146
Journal	SIAM Journal on Discrete Mathematics (SJDMEC)
Issue Number	3
Volume Number	27
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2013-08-13
Access Restriction	Subscribed
Subject Keyword	edit distance Symmetric groups transpositions symmetric group Combinatorics theoretical aspects of computational biology lower bounds Permutations, words, matrices
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in