BFWalk: backtrack-free network propagation with in-degree normalization

Abstract

Motivation In network medicine, the protein-protein interaction network, or interactome, is an essential resource for identifying candidate proteins underlying diseases and other phenotypic traits. Indeed, it can be leveraged via the guilt-by-association paradigm, which asserts that interacting proteins are likely to participate in the same molecular processes. Network propagation that combines the topology of the interactome with prior knowledge about disease genes is a promising strategy to identify new candidate genes contributing to diseases. However, existing network propagation algorithms are often biased toward highly connected proteins, called “hubs”. Results We present BFWalk, a novel network propagation algorithm designed to avoid inflated scores for hubs. We tested BFWalk across four human phenotypes: multiple morphological abnormalities of the sperm flagella, dyschromatopsia, hypertrophic cardiomyopathy, and chronic kidney disease. For each phenotype, we assessed whether BFWalk could recover known phenotype-associated genes and whether new candidate genes were enriched in relevant tissues. Depending on the phenotype, BFWalk outperformed or matched the state-of-the-art network propagation methods. Furthermore, the results confirmed that BFWalk is free of bias toward high-degree nodes. Therefore, BFWalk is a powerful method for identifying new genes across diverse phenotypes and constitutes a strong alternative to existing network propagation algorithms. Availability BFWalk is implemented in Python and C. The code is available under the GNU GPL (v3.0) on: https://github.com/jedrzejkubica/BFWalk Key Messages Existing network propagation algorithms are biased toward high-degree nodes. BFWalk is a novel network propagation algorithm designed to be free of this bias. BFWalk outperforms or matches the state-of-the-art methods, as shown by leave-one-out cross-validation and tissue enrichment analysis. Our method, validated using real public data, constitutes a major step forward in network propagation.