Optimal network alignment with graphlet degree vectors.
Optimal network alignment with graphlet degree vectors.
复制标题
DOI：
10.4137/cin.s4744
复制
发表时间：
2010-06-30
影响因子：
2
通讯作者：
Przulj N
中科院分区：
文献类型：
--
作者：
Milenković T;Ng WL;Hayes W;Przulj N
重要的生物信息被编码在生物网络的拓扑结构中。生物网络的比较分析被证明是有价值的，因为它们可以导致物种之间的知识转移，并对生物功能，疾病和进化提供更深入的见解。我们介绍了一种新的方法，使用匈牙利算法，以产生最佳的全球两个网络之间的对齐使用任何成本函数。我们设计了一个成本函数，仅基于网络拓扑结构，并使用它在我们的网络对齐。我们的方法可以应用于任何两个网络，而不仅仅是生物网络，因为它只基于网络拓扑结构。我们使用我们的新方法来对齐两个真核生物物种的蛋白质-蛋白质相互作用网络，并证明我们的对齐暴露了网络相似性的大而拓扑复杂的区域。同时，我们的比对在生物学上是有效的，因为许多比对的蛋白质对执行相同的生物学功能。从比对中，我们预测了尚未注释的蛋白质的功能，其中许多我们在文献中验证。此外，我们应用我们的方法来寻找不同物种的代谢网络之间的拓扑相似性，并根据我们的网络比对得分构建系统发育树。以这种方式获得的系统发育树承担一个惊人的相似之处，通过序列比对获得的。我们的方法在大型网络中检测具有统计意义的拓扑相似区域。它独立于蛋白质序列或网络拓扑外部的任何其他信息。
Important biological information is encoded in the topology of biological networks. Comparative analyses of biological networks are proving to be valuable, as they can lead to transfer of knowledge between species and give deeper insights into biological function, disease, and evolution. We introduce a new method that uses the Hungarian algorithm to produce optimal global alignment between two networks using any cost function. We design a cost function based solely on network topology and use it in our network alignment. Our method can be applied to any two networks, not just biological ones, since it is based only on network topology. We use our new method to align protein-protein interaction networks of two eukaryotic species and demonstrate that our alignment exposes large and topologically complex regions of network similarity. At the same time, our alignment is biologically valid, since many of the aligned protein pairs perform the same biological function. From the alignment, we predict function of yet unannotated proteins, many of which we validate in the literature. Also, we apply our method to find topological similarities between metabolic networks of different species and build phylogenetic trees based on our network alignment score. The phylogenetic trees obtained in this way bear a striking resemblance to the ones obtained by sequence alignments. Our method detects topologically similar regions in large networks that are statistically significant. It does this independent of protein sequence or any other information external to network topology.