A New Data-driven Deconvolution Algorithm For Noise Filtering In Biological Networks

Network is a good container to restore complex relationships in many fields like social, biological and information sciences. Although there was progress in complex network construction studies, real-world network is far more complicated. One of the challenging problem is the observed network is always inaccurate, contaminated by noise, consequently misleading the follow-up network analysis. So distinguishing the direct contacts from indirect ones is thus an important and tough task especially in the lack of prior knowledge.Among the noise in the reconstructed network, transitive noise is the mainly observed noise. Till now, only a few scientists like Jones D.T. have given an obscure concept: if there are true contacts between sites AB and BC, the transitive noise is the false observed correlation between AC. In order to filter this kind of noise, many groups in different fields have developed approaches using global optimization to solve this problem. For example, in protein residue contact map network, PSICOV uses inversed partial correlation matrix, and DCA employs Potts model. Comparing to these approaches applied in specific fields, the network deconvolution(ND) formulates the problem as the inverse of network convolution. But ND doesn`t simulate the transitive noise precisely and relies on an optimized parameter.To solve the application-limited and parameter-dependent problems existing in current methods, for the first time, using information theory and graph theory, we build the theory frame of graph information field, analyze the production mechanism of transitive noise, give a specific definition of transitive noise, build a noise model to simulate the transitive noise, and propose Balanced Network Deconvolution(BND) to filter transitive noise. Transitive noise is actually a kind of false-positive noise due to the bi-direction information conduction through the indirect paths between sites. ‘Balanced’ means BND is based on a balanced noise model and keeps the balanced distribution of eigenvalues. BND is very convenient for usage without the dependence on optimized parameters.To test the performance of BND, we exploit three network systems, from protein residue-residue contact maps in CASP 9/10 and PSICOV datasets, the gene regulation networks in single-celled eukaryote Saccharomyces cerevisiae and the bacterium Escherichia coli, and two kinds of co-authorship social networks, with the purpose of identifying true contacts and strong interactions by filtering the transitive noises from the networks. The abundant experimental results show BND`s advantage over parameter-dependent ND as a general tool. And compared to other transitive noise filters developed in specific fields, BND can improve the quality of constructed network as a post-processing. To sum up, BND can achieve high network qualities and have robust general application ability without optimized parameters.