On the average number of reversals needed to sort signed permutations

The recurrence formula is built based on the analysis of the probability that two nodes of the breakpoint graph belong to the same alternating cycle among all the breakpoint graphs related with permutations of length n. Through this analysis it is possible to compute the average reversal distance for signed variations of the identity permutation. Also, lower and upper bounds of the average reversal distance for signed permutations are provided. Additionally, based on computational data, it is shown how these bounds can be used in order to propose concrete upper and lower bounds.