RedNemo: topology-based PPI network reconstruction via repeated diffusion with neighborhood modifications

Abstract

Motivation: Analysis of protein-protein interaction (PPI) networks provides invaluable insight into several systems biology problems. High-throughput experimental techniques together with computational methods provide large-scale PPI networks. However a major issue with these networks is their erroneous naturethey contain false-positive interactions and usually many more false-negatives. Recently several computational methods have been proposed for network reconstruction based on topology where given an input PPI network the goal is to reconstruct the network by identifying false-positives/-negatives as correctly as possible. Results: We observe that the existing topology-based network reconstruction algorithms suffer several shortcomings. An important issue is regarding the scalability of their computational requirements especially in terms of execution times with the network sizes. They have only been tested on small-scale networks thus far and when applied on large-scale networks of popular PPI databases the executions require unreasonable amounts of time or may even crash without producing any output for some instances even after several months of execution. We provide an algorithm RedNemo for the topology-based network reconstruction problem. It provides more accurate networks than the alternatives as far as biological qualities measured in terms of most metrics based on gene ontology annotations. The recovery of a high-confidence network modified via random edge removals and rewirings is also better with RedNemo than with the alternatives under most of the experimented removal/rewiring ratios. Furthermore through extensive tests on databases of varying sizes we show that RedNemo achieves these results with much better running time performances.