Efficient, robust and effective rank aggregation for massive biological datasets

Pierre Andrieu (1) , Bryan Brancotte (2) , Laurent Bulteau (3) , Sarah Cohen-Boulakia (1) , Alain Denise (1, 4) , Adeline Pierrot (1) , Stéphane Vialette (3)

1 LISN - Laboratoire Interdisciplinaire des Sciences du Numérique
2 Hub Bioinformatique et Biostatistique - Bioinformatics and Biostatistics HUB
3 LIGM - Laboratoire d'Informatique Gaspard-Monge
4 I2BC - Institut de Biologie Intégrative de la Cellule

Massive biological datasets are available in various sources. To answer a biological question (e.g., ''which are the genes involved in a given disease?''), life scientists query and mine such datasets using various techniques. Each technique provides a list of results usually ranked by importance (e.g., a list of ranked genes). Combining the results obtained by various techniques, that is, combining ranked lists of elements into one list of elements is of paramount importance to help life scientists make the most of various results and prioritize further investigations. Rank aggregation techniques are particularly well-fitted with this context as they take in a set of rankings and provide a consensus, that is, a single ranking which is the ''closest'' to the input rankings. However, (i) the problem of rank aggregation is NP-hard in most cases (using an exact algorithm is currently not possible for more than a few dozens of elements) and (ii) several (possibly very different) exact solutions can be obtained. As answer to (i), many heuristics and approximation algorithms have been proposed. However, heuristics cannot guarantee how far from an exact solution the consensus ranking will be, and the approximation ratio of approximation algorithms dedicated to the problem is fairly high (not less than 3/2). No solution has yet been proposed to help true-users dealing with the problem encountered in point (ii). In this paper we present a complete system able to perform rank aggregation of massive biological datasets. Our solution is efficient as it is based on an original partitioning method making it possible to compute a high-quality consensus using an exact algorithm in a large number of cases. Our solution is robust as it clearly identifies for the user groups of elements whose relative order is the same in any optimal solution. These features provide answers to points (i) and (ii) and lie in mathematical bases offering guarantees on the computed result. Also, our solution is effective as it has been implemented into a real tool, ConquR-BioV2 is used for the life science community, and evaluated at large-scale using a very large number of datasets.

Mots clés: Rank aggregation; Consensus ranking; Massive biological datasets; Kemeny rule

Domaines: Complexité [cs.CC]; Bio-informatique [q-bio.QM]; Algorithme et structure de données [cs.DS]

Pierre Andrieu, Bryan Brancotte, Laurent Bulteau, Sarah Cohen-Boulakia, Alain Denise, et al.. Efficient, robust and effective rank aggregation for massive biological datasets. Future Generation Computer Systems, 2021, 124, pp.406-421. ⟨10.1016/j.future.2021.06.013⟩. ⟨hal-03388443⟩