Department of Computer Science and Technology, Tsinghua University, 1207B Zijing Building 15#, Beijing 100084, China.
IEEE/ACM Trans Comput Biol Bioinform. 2011 May-Jun;8(3):621-34. doi: 10.1109/TCBB.2010.78.
The emergence of high-throughput technologies leads to abundant protein-protein interaction (PPI) data and microarray gene expression profiles, and provides a great opportunity for the identification of novel protein complexes using computational methods. By combining these two types of data, we propose a novel Graph Fragmentation Algorithm (GFA) for protein complex identification. Adapted from a classical max-flow algorithm for finding the (weighted) densest subgraphs, GFA first finds large (weighted) dense subgraphs in a protein-protein interaction network, and then, breaks each such subgraph into fragments iteratively by weighting its nodes appropriately in terms of their corresponding log-fold changes in the microarray data, until the fragment subgraphs are sufficiently small. Our tests on three widely used protein-protein interaction data sets and comparisons with several latest methods for protein complex identification demonstrate the strong performance of our method in predicting novel protein complexes in terms of its specificity and efficiency. Given the high specificity (or precision) that our method has achieved, we conjecture that our prediction results imply more than 200 novel protein complexes.
高通量技术的出现带来了丰富的蛋白质-蛋白质相互作用（PPI）数据和基因表达微阵列谱，为使用计算方法识别新的蛋白质复合物提供了绝佳的机会。通过结合这两种类型的数据，我们提出了一种新的图碎片算法（GFA）用于蛋白质复合物的识别。GFA 源自一种用于寻找（加权）密度最大子图的经典最大流算法，它首先在蛋白质-蛋白质相互作用网络中找到大的（加权）密集子图，然后通过根据微阵列数据中相应的对数倍数变化适当加权其节点，将每个这样的子图迭代地分解为碎片，直到碎片子图足够小。我们在三个广泛使用的蛋白质-蛋白质相互作用数据集上的测试和与几种最新的蛋白质复合物识别方法的比较表明，我们的方法在预测新的蛋白质复合物方面具有很强的性能，无论是特异性还是效率方面。鉴于我们的方法已经达到了很高的特异性（或精度），我们推测我们的预测结果意味着有超过 200 个新的蛋白质复合物。
