Rank aggregation methods

This article provides an overview of rank aggregation methods and algorithms, with an emphasis on modern biological applications. Rank aggregation methods have traditionally been used extensively in marketing and advertisement research, and in applied psychology in general. In recent years, rank aggregation methods have emerged as an important tool for combining information from different Internet search engines or from different omics-scale biological studies. We discuss three classes of methods, namely distributional based, heuristic, and stochastic search. The original Thurstone's scaling and its extensions represent the first class of methods that are most appropriate for aggregating many short ranked lists. Aggregating results from consumer rankings of products falls into this category of problems. Its application to biological problems is also being explored. On the other hand, heuristic algorithms and stochastic search methods are applicable to the situation of aggregating a small number of long lists, the so-called 'high-level' meta-analysis scenario. Combining results from different search engines/criteria and a number of omics-scale biological applications fall into this category. Heuristic algorithms are deterministic in nature, ranging from simple arithmetic averages of ranks to Markov chains and stationary distributions. Stochastic search algorithms, on the other hand, aim at maximizing a particular criterion such as that following the Kemeny guideline. Several examples will be provided to illustrate, compare, and contrast the methods and algorithms. The examples range from simple and contrive to representing realistic scenarios. In particular, an application to aggregating results from gene expression microarray studies is provided to demonstrate applications of the methods to modern biological problems. (C) 2010 John Wiley & Sons, Inc.