Parking Functions, Labeled Trees and DCJ Sorting Scenarios

Abstract. In genome rearrangement theory, one of the elusive questions raised in recent years is the enumeration of rearrangement scenarios be-tween two genomes. This problem is related to the uniform generation of rearrangement scenarios, and the derivation of tests of statistical signifi-cance of the properties of these scenarios. Here we give an exact formula for the number of double-cut-and-join (DCJ) rearrangement scenarios of co-tailed genomes. We also construct effective bijections between the set of scenarios that sort a cycle and well studied combinatorial objects such as parking functions and labeled trees.