Constrained Rank Aggregation with Applications to Gene Prioritization

Dr. Olgica Milenkovic
University of Illinois Urbana-Champaign

Abstract
Joint work with Farzad Farnoud, Minji Kim and Fardad Raisali
The problem of rank aggregation arises in research areas as diverse as computer science, social sciences, management, and marketing. Rank aggregation may be succinctly described as follows: given a set of rankings, each produced by an expert, find the ranking that minimizes the sum of the distances to the original rankings. Here, the distance function is chosen according to some predefined relevance criteria, such as similarity of ranked subjects and cut-off thresholds for the rankings.

In most rank aggregation scenarios, one uses Kendall’s tau distance which leads to Kemeny optimal orderings. Although Kendall’s tau and many other classical distance functions, including Spearman’s Footrule, are well established and well studied, they cannot take into account two important factors in rank aggregation. First, for some applications, the top of the list is more important than the bottom of the list, and hence changes to the top of the list must be compensated for by larger induced distances. Second, if one were to ensure diversity of the list of candidates, transposing elements that are similar must be less costly than transposing dissimilar elements.

In this talk, we propose a distance function, termed weighted Cayley distance, based on transpositions with non-uniform costs that enables us to address the top-bottom and similarity problems. Many of the previously proposed distance functions may be viewed as a specialization of the proposed distance function. We also describe a polynomial time algorithm for computing the general form of this distance function using a variety of tools from graph theory and optimization theory. Furthermore, we propose a number of rank aggregation methods for the weighted Cayley distance and illustrate how to use the methods for ranking genes according to their likelihood of being involved in a disease.

Biography
Olgica Milenkovic received her MS Degree in Mathematics and PhD in Electrical Engineering from the University of Michigan, Ann Arbor, in 2001 and 2002, respectively. From 2002 until 2006, she was with the faculty of Electrical Engineering, University of Colorado, Boulder. In 2007, she joined the University of Illinois, Urbana-Champaign.
Her research interests are in bioinformatics, coding theory, compressive sensing and social sciences.

Olgica Milenkovic is a recipient of the NSF Career Award, the DARPA Young Faculty Award, and the Dean's Excellence in Research Award. In 2012 she was named a Center for Advanced Studies (CAS) Associate, and in 2013 she was named a Willet scholar. From 2006, she served on the editorial board for the Transactions on Communication, Transactions on Signal Processing and Transactions on Information Theory.