Some enumeration results for sorting signed permutations by reversals

A signed permutation is a permutation of the numbers 1 through n in which each number is signed. A reversal of a signed permutation is the act of swapping the order of a consecutive subsequence of numbers and changing the sign of each number in the subsequence. Given a signed permutation π, it is always possible to transform π into the identity permutation using a sequence of reversals. This process of transforming a signed permutation into the identity permutation is referred to as sorting by reversals. The reversal distance of signed permutation π is the minimum number of reversals required to transform π into the identity permutation. Signed permutations, and their reversals, are useful tools in the comparative study of genomes. Different species often share similar genes that were inherited from common ancestors. However, these genes have been shuffled by mutations that modified the content of the chromosomes, the order of genes within a particular chromosome, and/or the orientation of a gene. Comparing two sets of similar genes appearing along a chromosome in two different species yields two signed permutations. The reversal distance between these two signed permutations provides a good estimate of the genetic distance between the two species. For example, the genomes for cabbage and turnip differ by three reversals while the genomes for a human and a mouse differ by 251 rearrangements, 149 of which are reversals.  In this talk, we will discuss several enumeration results concerning the number of signed permutations of a fixed reversal distance.