Approximating the number of Double Cut-and-Join scenarios

The huge number of solutions in genome rearrangement problems calls for algorithms for counting and sampling in the space of solutions, rather than drawing one arbitrary scenario. A closed formula exists for counting the number of scenarios between co-tailed genomes, but no polynomial result has been published so far for arbitrary genomes. We prove here that it admits a Fully Polynomial time Randomized Approximation Scheme. We use an almost uniform sampler and prove that it converges to the uniform distribution in fully polynomial time. The can be used to quickly draw a sample of scenarios from a prescribed distribution and test some hypotheses on genome evolution.