On the expectation and variance of the reversal distance

Acta Univ Sapientiae Matem. 2009 Jan 1;1(1):5-20.

Abstract

We give a pair of well-matched lower and upper bounds for the expectation of reversal distance under the hypothesis of random gene order by investigating the expected number of cycles in the breakpoint graph of linear signed permutations. Sankoff and Haque [9] proved similar results for circular signed permutations based on approximations based on a slightly different model; while our approach is discrete. We also provide an near-tight upper bound for the variance of reversal distance, which gives information on the distribution of reversal distance.