  The Single Cut or Join (SCJ) operation on genomes, generalizing chromosome
evolution by fusions and fissions, is the computationally simplest known model
of genome rearrangement. While most genome rearrangement problems are already
hard when comparing three genomes, it is possible to compute in polynomial time
a most parsimonious SCJ scenario for an arbitrary number of genomes related by
a binary phylogenetic tree.
  Here we consider the problems of sampling and counting the most parsimonious
SCJ scenarios. We show that both the sampling and counting problems are easy
for two genomes, and we relate SCJ scenarios to alternating permutations.
However, for an arbitrary number of genomes related by a binary phylogenetic
tree, the counting and sampling problems become hard. We prove that if a Fully
Polynomial Randomized Approximation Scheme or a Fully Polynomial Almost Uniform
Sampler exist for the most parsimonious SCJ scenario, then RP = NP.
  The proof has a wider scope than genome rearrangements: the same result holds
for parsimonious evolutionary scenarios on any set of discrete characters.

Computational Engineering, Finance, and Science