Consensus Ranking with Signed Permutations


Raman Arora, Marina Meila ;
Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, PMLR 31:117-125, 2013.


Signed permutations (also known as the hyperoctahedral group) are used in modeling genome rearrangements. The algorithmic problems they raise are computationally demanding when not NP-hard. This paper presents a tractable algorithm for learning consensus ranking between signed permutations under the inversion distance. This can be extended to estimate a natural class of exponential models over the group of signed permutations. We investigate experimentally the efficiency of our algorithm for modeling data generated by random reversals.

Related Material