Natalie 2.0: Sparse Global Network Alignment as a Special Case of Quadratic Assignment
Natalie 2.0: Sparse Global Network Alignment as a Special Case of Quadratic Assignment
复制标题
DOI：
10.3390/a8041035
复制
发表时间：
2015-12-01
期刊：
影响因子：
2.3
通讯作者：
Klau, Gunnar W.
中科院分区：
文献类型：
--
作者：
El-Kebir, Mohammed;Heringa, Jaap;Klau, Gunnar W.
关于分子相互作用的数据正在以惊人的速度增长，而用于分析这些网络数据的可靠方法的开发仍然滞后。这尤其适用于比较网络分析领域，人们想要确定生物网络之间的共性。由于生物功能主要在网络级别运行，因此显然需要拓扑感知的比较方法。我们提出了一种快速、稳健的全局网络比对方法，该方法可以灵活地处理各种计分方案，同时考虑到节点之间的对应关系以及网络拓扑结构。我们利用网络对齐是研究得很好的二次指派问题(QAP)的特例。我们的重点是稀疏网络对齐，其中每个节点只能映射到另一个网络中通常很小的节点子集。这对应于一个具有对称稀疏权重矩阵的QAP实例。我们通过改进拉格朗日松弛方法得到了问题的强上、下界，并介绍了开源软件工具Natalie2.0，它是我们方法的公开实现。在对六个不同物种的蛋白质相互作用网络的广泛计算研究中，我们发现我们的新方法优于替代的已建立的和最近最先进的方法。
Data on molecular interactions is increasing at a tremendous pace, while the development of solid methods for analyzing this network data is still lagging behind. This holds in particular for the field of comparative network analysis, where one wants to identify commonalities between biological networks. Since biological functionality primarily operates at the network level, there is a clear need for topology-aware comparison methods. We present a method for global network alignment that is fast and robust and can flexibly deal with various scoring schemes taking both node-to-node correspondences as well as network topologies into account. We exploit that network alignment is a special case of the well-studied quadratic assignment problem (QAP). We focus on sparse network alignment, where each node can be mapped only to a typically small subset of nodes in the other network. This corresponds to a QAP instance with a symmetric and sparse weight matrix. We obtain strong upper and lower bounds for the problem by improving a Lagrangian relaxation approach and introduce the open source software tool Natalie 2.0, a publicly available implementation of our method. In an extensive computational study on protein interaction networks for six different species, we find that our new method outperforms alternative established and recent state-of-the-art methods.