UC Irvine

An efficient and reliable network alignment serves to find the mapping with maximum similarity between different networks, which is a way to improve our understanding of biology system and biological process. To build such network alignment is a foremost challenging task in computational biology because it involves the bipartite graph matching problem, which is an NP-hard problem. In this work, we propose a novel global biomolecular network alignment method named NFMA. Based on the minimum cost maximum flow problem (MCMFP) of network flow model, NFMA introduces opposite numbers to address the maximum cost problem so that the new model can get the alignment with maximum similarity. Furthermore, based on the existing method used to describe topological structure in undirected network, we present a new measure to identify topological information in directed network, which enables NFMA to extend to alignment in directed network. We conduct three experiments on classical yeast protein-protein interaction networks (PINs) and human PINs. We compare NFMA with other 7 eminent algorithms, and prove that NFMA can obtain an efficient and meaningful alignment which takes both biological similarity and topological similarity into consideration, and the time efficiency of NFMA is also outstanding in that it only takes approximately 250 seconds to get an accurate alignment when aligning two large networks.