Center for Bioinformatics and Computational Biology, Institute for Advanced Computer Studies and Department of Computer Science, University of Maryland, College Park, MD 20742, USA.
Bioinformatics. 2012 Dec 1;28(23):3105-14. doi: 10.1093/bioinformatics/bts592. Epub 2012 Oct 9.
Protein interaction networks provide an important system-level view of biological processes. One of the fundamental problems in biological network analysis is the global alignment of a pair of networks, which puts the proteins of one network into correspondence with the proteins of another network in a manner that conserves their interactions while respecting other evidence of their homology. By providing a mapping between the networks of different species, alignments can be used to inform hypotheses about the functions of unannotated proteins, the existence of unobserved interactions, the evolutionary divergence between the two species and the evolution of complexes and pathways.
We introduce GHOST, a global pairwise network aligner that uses a novel spectral signature to measure topological similarity between subnetworks. It combines a seed-and-extend global alignment phase with a local search procedure and exceeds state-of-the-art performance on several network alignment tasks. We show that the spectral signature used by GHOST is highly discriminative, whereas the alignments it produces are also robust to experimental noise. When compared with other recent approaches, we find that GHOST is able to recover larger and more biologically significant, shared subnetworks between species.
An efficient and parallelized implementation of GHOST, released under the Apache 2.0 license, is available at http://cbcb.umd.edu/kingsford_group/ghost
蛋白质相互作用网络为生物过程提供了重要的系统级视图。生物网络分析中的一个基本问题是一对网络的全局对齐，即将一个网络的蛋白质与另一个网络的蛋白质以一种在保留它们的相互作用的同时尊重它们同源性的其他证据的方式进行对应。通过为不同物种的网络提供映射，可以将对齐用于推断未注释蛋白质的功能、未观察到的相互作用的存在、两个物种之间的进化分歧以及复合物和途径的进化。
我们引入了 GHOST，一种全局成对网络对齐器，它使用新的谱特征来测量子网之间的拓扑相似性。它结合了种子和扩展的全局对齐阶段和局部搜索过程，并在几个网络对齐任务上超过了最新技术水平。我们表明，GHOST 使用的谱特征具有高度的辨别力，而它生成的对齐也对实验噪声具有鲁棒性。与其他最近的方法相比，我们发现 GHOST 能够在物种之间恢复更大和更具生物学意义的共享子网。
GHOST 的高效和并行实现，根据 Apache 2.0 许可证发布，可在 http://cbcb.umd.edu/kingsford_group/ghost 获得。
