• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>IEEE International Conference on Bioinformatics and Biomedicine >A global biomolecular network alignment method based on network flow model
【24h】

A global biomolecular network alignment method based on network flow model

机译：基于网络流模型的全球生物分子网络比对方法

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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.
机译：有效且可靠的网络对齐有助于找到不同网络之间具有最大相似性的映射，这是一种增进我们对生物学系统和生物学过程的理解的方式。建立这样的网络对齐是计算生物学中最艰巨的任务，因为它涉及二部图匹配问题，这是一个NP难题。在这项工作中，我们提出了一种新的全球生物分子网络比对方法，称为NFMA。 NFMA基于网络流模型的最小成本最大流问题（MCMFP），引入了相反的数字来解决最大成本问题，从而使新模型可以获得具有最大相似度的对齐方式。此外，基于用于描述无向网络中拓扑结构的现有方法，我们提出了一种新方法来识别有向网络中的拓扑信息，这使NFMA能够扩展到有向网络中的对齐方式。我们对经典的酵母蛋白质-蛋白质相互作用网络（PINs）和人类PINs进行了三个实验。我们将NFMA与其他7种著名算法进行了比较，并证明NFMA可以获得兼具生物学相似性和拓扑相似性的高效且有意义的比对，并且NFMA的时间效率也非常出色，因为仅需约250秒即可获得对齐两个大型网络时的精确对齐。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号