Combinatorics of Permutations, 3rd Edition

9How Did We Get Here? Permutations as Genome Rearrangements.

DOI: 10.1201/9780429274107-9

9.1 Introduction

Let p and q be two permutations, written in one-line notation. In this section, we will attempt to transform p into q using only certain kinds of allowed steps. If k is the smallest integer so that p can be transformed into q using k allowed steps, then we say that the distance $d(p,q)$ of p and q is k.

The motivation for this research comes from molecular biology, where genomes of various species can be modeled by permutations, and the distance between these permutations can be interpreted as the evolutionary distance between species. A classic paper of the field, by Shridhar Hannenhalli and Pavel Pevzner [211], is entitled Transforming ...