2015/02/27 by Ricky X. F. Chen, Chen, Ricky X. F., Christian M. Reidys +1
Agricultural and Biological Sciences · Biochemistry, Genetics and Molecular Biology · Computer Science · #05A05 #92B05 #Algorithms and Data Compression #Chromosomal and Genetic Variations #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Genome Rearrangement Algorithms #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.1502.07971
openalex publication_date 2015/02/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper we present a simple framework to study various distance problems of permutations, including the transposition and block-interchange distance of permutations as well as the reversal distance of signed permutations. These problems are very important in the study of the evolution of genomes. We give a general formulation for lower bounds of the transposition and block-interchange distance from which the existing lower bounds obtained by Bafna and Pevzner, and Christie can be easily derived. As to the reversal distance of signed permutations, we translate it into a block-interchange distance problem of permutations so that we obtain a new lower bound. Furthermore, studying distance problems via our framework motivates several interesting combinatorial problems related to product of permutations, some of which are studied in this paper as well.