Protein Mover's Distance: A Geometric Framework for Solving Global Alignment of PPI Networks
Protein Mover's Distance: A Geometric Framework for Solving Global Alignment of PPI Networks
复制标题
DOI：
10.1007/978-3-319-71150-8_5
复制
发表时间：
2017-12
期刊：
影响因子：
--
通讯作者：
Manni Liu;Hu Ding
中科院分区：
文献类型：
--
作者：
Manni Liu;Hu Ding
蛋白质-蛋白质相互作用（PPI）网络是表示蛋白质之间相互作用的无权无向图，其中每个节点表示一种蛋白质，连接两个节点的每个边表示它们之间的相互作用。给定两个PPI网络，找到它们的对齐是一个基本问题，在生物信息学中有许多重要的应用。然而，它往往需要解决一些具有挑战性和np困难的广义子图同构问题。根据我们之前的几何方法[21]，我们提出了一个统一的PPI网络对齐算法框架。我们首先定义了一个称为“蛋白质移动距离（PMD）”的一般概念，以评估两个PPI网络的对齐。PMD类似于众所周知的“地球移动距离”；然而，我们也纳入了其他一些信息，如蛋白质的功能注释。我们的算法框架包括两个步骤：嵌入和匹配。在嵌入步骤中，我们采用了三种不同的图嵌入技术来保留原始PPI网络的拓扑结构。在匹配步骤中，我们计算了一个嵌入式PPI网络的刚性变换，以最小化其对另一个PPI网络的PMD；通过使用结果PMD的流值作为匹配分数，我们能够获得所需的对齐。此外，我们的框架可以很容易地扩展到多个PPI网络的联合校准。在两个流行的基准数据集上的实验结果表明，我们的方法在对齐质量方面优于现有的方法。
A protein-protein interaction (PPI) network is an unweighted and undirected graph representing the interactions among proteins, where each node denotes a protein and each edge connecting two nodes indicates their interaction. Given two PPI networks, finding their alignment is a fundamental problem and has many important applications in bioinformatics. However, it often needs to solve some generalized version of subgraph isomorphism problem which is challenging and NP-hard. Following our previous geometric approach [21], we propose a unified algorithmic framework for PPI networks alignment. We first define a general concept called “Protein Mover’s Distance (PMD)” to evaluate the alignment of two PPI networks. PMD is similar to the well known “Earth Mover’s Distance”; however, we also incorporate some other information, e.g., the functional annotation of proteins. Our algorithmic framework consists of two steps, Embedding and Matching. For the embedding step, we apply three different graph embedding techniques to preserve the topological structures of the original PPI networks. For the matching step, we compute a rigid transformation for one of the embedded PPI networks so as to minimize its PMD to the other PPI network; by using the flow values of the resulting PMD as the matching scores, we are able to obtain the desired alignment. Also, our framework can be easily extended to joint alignment of multiple PPI networks. The experimental results on two popular benchmark datasets suggest that our method outperforms existing approaches in terms of the quality of alignment.