Fitting a geometric graph to a protein-protein interaction network
Fitting a geometric graph to a protein-protein interaction network
复制标题
DOI：
10.1093/bioinformatics/btn079
复制
发表时间：
2008-04-15
期刊：
影响因子：
5.8
通讯作者：
Przulji, Natasa
中科院分区：
文献类型：
--
作者：
Higham, Desmond J.;Rasajski, Marija;Przulji, Natasa
动机：为蛋白质相互作用(PPI)网络找到一个好的网络零模型是一个基本问题。这样的模型将对网络结构和生物功能之间的相互作用以及进化提供洞察力。此外，网络(图)模型被用来指导生物实验和发现新的生物特征。几何随机图是PPI网络的一种很好的模型。在几何随机图中，节点对应于度量空间中均匀随机分布的点，度量空间中对应点按一定距离范数足够接近的节点对之间存在边(链)。计算实验表明，PPI网络的关键拓扑性质与几何随机图模型具有较好的匹配关系。在这项工作中，我们利用了几何性质可以直接测试的事实，进一步推动了比较。为此，我们开发了一种算法，该算法获取PPI相互作用数据并将蛋白质嵌入到低维欧几里德空间中，前提是连通性信息对应于欧几里德邻近度，就像几何随机图一样。通过计算受试者操作员特征(ROC)曲线下面积来判断拟合的敏感性和特异性。网络嵌入算法基于多维尺度，以网络中路径长度的平方根作为欧氏空间中的欧几里德距离。该算法利用稀疏性提高计算效率，只需要少量的稀疏矩阵乘法运算，复杂度为O(N-2)，其中N是蛋白质的个数。结果：该算法在人工构建的几何网络中成功地重新发现了几何结构，即使通过重新布线某些链路来添加噪声也是如此。将该算法应用于19个公开可用的不同生物体的PPI网络，结果表明：(A)存在几何效应；(B)二维欧氏空间通常与高维欧氏空间一样有效地解释连通性。在高置信度酵母数据集上的测试产生了非常强烈的几何结构指示(ROC曲线下的面积为0.89)，该网络基本上与噪声的几何网络没有区别。总体而言，这些结果支持了PPI网络具有几何结构的假设。
Motivation: Finding a good network null model for proteinprotein interaction (PPI) networks is a fundamental issue. Such a model would provide insights into the interplay between network structure and biological function as well as into evolution. Also, network (graph) models are used to guide biological experiments and discover new biological features. It has been proposed that geometric random graphs are a good model for PPI networks. In a geometric random graph, nodes correspond to uniformly randomly distributed points in a metric space and edges (links) exist between pairs of nodes for which the corresponding points in the metric space are close enough according to some distance norm. Computational experiments have revealed close matches between key topological properties of PPI networks and geometric random graph models. In this work, we push the comparison further by exploiting the fact that the geometric property can be tested for directly. To this end, we develop an algorithm that takes PPI interaction data and embeds proteins into a low-dimensional Euclidean space, under the premise that connectivity information corresponds to Euclidean proximity, as in geometric-random graphs. We judge the sensitivity and specificity of the fit by computing the area under the Receiver Operator Characteristic (ROC) curve. The network embedding algorithm is based on multi-dimensional scaling, with the square root of the path length in a network playing the role of the Euclidean distance in the Euclidean space. The algorithm exploits sparsity for computational efficiency, and requires only a few sparse matrix multiplications, giving a complexity of O(N-2) where N is the number of proteins.Results: The algorithm has been verified in the sense that it successfully rediscovers the geometric structure in artificially constructed geometric networks, even when noise is added by re-wiring some links. Applying the algorithm to 19 publicly available PPI networks of various organisms indicated that: (a) geometric effects are present and (b) two-dimensional Euclidean space is generally as effective as higher dimensional Euclidean space for explaining the connectivity. Testing on a high-confidence yeast data set produced a very strong indication of geometric structure (area under the ROC curve of 0.89), with this network being essentially indistinguishable from a noisy geometric network. Overall, the results add support to the hypothesis that PPI networks have a geometric structure.