Approximating the number of double cut-and-join scenarios (Q441869)

In the present paper, the authors study the problem of counting the number of DCJ scenarios between two genomes represented as sets of paths and cycles. The problem is of importance: if determining the DCJ distance is easy (there exists a closed formula), knowing the number of scenarios that satisfy this distance, and, more importantly, being able to provide a sample of the most likely ones, is a problem that needs to be studied in more depth. The authors show the following results: 1) counting the number of optimal DCJ scenarios admits a fully polynomial time randomized approximation scheme (FPRAS); 2) there exists an MCMC uniform sampler that approximates this number; 3) this MCMC converges to the uniform distribution in fully polynomial time. In particular, the latter two results can be used to generate a sample of DCJ scenarios from a given distribution, in order to test some hypotheses on genome evolution. Due to the subjects covered by the authors in this paper, one needs to be familiar with genome rearrangements (and especially DCJ), complexity classes, and probabilities. However, the paper is cautiously written and is pleasant for the informed reader.