Skip to main content
eScholarship
Open Access Publications from the University of California

UC Irvine

UC Irvine Previously Published Works bannerUC Irvine

A global biomolecular network alignment method based on network flow model

  • Author(s): Xie, J;
  • Li, J;
  • Wang, J;
  • Nie, Q;
  • Zhang, W
  • et al.
Abstract

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.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Main Content
For improved accessibility of PDF content, download the file to your device.
Current View