School of Computer Science and Technology, Xidian University, 710071, China.
School of Computer Science and Technology, Xi'an University of Technology, 710048, China.
Proteome Sci. 2012 Jun 21;10 Suppl 1(Suppl 1):S16. doi: 10.1186/1477-5956-10-S1-S16.
Network alignment is one of the most common biological network comparison methods. Aligning protein-protein interaction (PPI) networks of different species is of great important to detect evolutionary conserved pathways or protein complexes across species through the identification of conserved interactions, and to improve our insight into biological systems. Global network alignment (GNA) problem is NP-complete, for which only heuristic methods have been proposed so far. Generally, the current GNA methods fall into global heuristic seed-and-extend approaches. These methods can not get the best overall consistent alignment between networks for the opinionated local seed. Furthermore These methods are lost in maximizing the number of aligned edges between two networks without considering the original structures of functional modules.
We present a novel seed selection strategy for global network alignment by constructing the pairs of hub nodes of networks to be aligned into multiple seeds. Beginning from every hub seed and using the membership similarity of nodes to quantify to what extent the nodes can participate in functional modules associated with current seed topologically we align the networks by modules. By this way we can maintain the functional modules are not damaged during the heuristic alignment process. And our method is efficient in resolving the fatal problem of most conventional algorithms that the initialization selected seeds have a direct influence on the alignment result. The similarity measures between network nodes (e.g., proteins) include sequence similarity, centrality similarity, and dynamic membership similarity and our algorithm can be called Multiple Hubs-based Alignment (MHA).
When applying our seed selection strategy to several pairs of real PPI networks, it is observed that our method is working to strike a balance, extending the conserved interactions while maintaining the functional modules unchanged. In the case study, we assess the effectiveness of MHA on the alignment of the yeast and fly PPI networks. Our method outperforms state-of-the-art algorithms at detecting conserved functional modules and retrieves in particular 86% more conserved interactions than IsoRank.
We believe that our seed selection strategy will lead us to obtain more topologically and biologically similar alignment result. And it can be used as the reference and complement of other heuristic methods to seek more meaningful alignment results.
网络对齐是最常见的生物网络比较方法之一。对齐不同物种的蛋白质-蛋白质相互作用（PPI）网络对于通过识别保守相互作用在物种间检测进化保守途径或蛋白质复合物，以及提高我们对生物系统的认识非常重要。全局网络对齐（GNA）问题是 NP 完全的，迄今为止仅提出了启发式方法。通常，当前的 GNA 方法属于全局启发式种子和扩展方法。由于有偏见的局部种子，这些方法不能在网络之间获得最佳的整体一致对齐。此外，这些方法在最大化两个网络之间对齐边的数量时没有考虑到功能模块的原始结构，因此会丢失信息。
我们通过构建要对齐的网络的枢纽节点对来提出一种新的全局网络对齐种子选择策略，将其分为多个种子。从每个枢纽种子开始，并使用节点的成员相似性来量化节点在拓扑上参与与当前种子相关的功能模块的程度，我们通过模块对齐网络。通过这种方式，我们可以在启发式对齐过程中保持功能模块不受损坏。并且我们的方法在解决大多数常规算法的致命问题方面非常有效，即所选种子的初始化直接影响对齐结果。网络节点（例如蛋白质）之间的相似性度量包括序列相似性、中心性相似性和动态成员相似性，我们的算法可以称为基于多个枢纽的对齐（MHA）。
当将我们的种子选择策略应用于几对真实的 PPI 网络时，观察到我们的方法正在努力取得平衡，在扩展保守相互作用的同时保持功能模块不变。在案例研究中，我们评估了 MHA 在酵母和果蝇 PPI 网络对齐中的有效性。与最先进的算法相比，我们的方法在检测保守功能模块方面表现更好，并且特别比 IsoRank 检索到更多的保守相互作用（86%）。
我们相信，我们的种子选择策略将使我们获得更具拓扑和生物学相似性的对齐结果。并且可以作为其他启发式方法的参考和补充，以寻求更有意义的对齐结果。
