Consensus Ranking with Signed Permutations

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

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v31-arora13a, title = {Consensus Ranking with Signed Permutations}, author = {Arora, Raman and Meilă, Marina}, booktitle = {Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics}, pages = {117--125}, year = {2013}, editor = {Carvalho, Carlos M. and Ravikumar, Pradeep}, volume = {31}, series = {Proceedings of Machine Learning Research}, address = {Scottsdale, Arizona, USA}, month = {29 Apr--01 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v31/arora13a.pdf}, url = {https://proceedings.mlr.press/v31/arora13a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Consensus Ranking with Signed Permutations %A Raman Arora %A Marina Meilă %B Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2013 %E Carlos M. Carvalho %E Pradeep Ravikumar %F pmlr-v31-arora13a %I PMLR %P 117--125 %U https://proceedings.mlr.press/v31/arora13a.html %V 31 %X 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.
RIS
TY - CPAPER TI - Consensus Ranking with Signed Permutations AU - Raman Arora AU - Marina Meilă BT - Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics DA - 2013/04/29 ED - Carlos M. Carvalho ED - Pradeep Ravikumar ID - pmlr-v31-arora13a PB - PMLR DP - Proceedings of Machine Learning Research VL - 31 SP - 117 EP - 125 L1 - http://proceedings.mlr.press/v31/arora13a.pdf UR - https://proceedings.mlr.press/v31/arora13a.html AB - 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. ER -
APA
Arora, R. & Meilă, M.. (2013). Consensus Ranking with Signed Permutations. Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 31:117-125 Available from https://proceedings.mlr.press/v31/arora13a.html.

Related Material