IEEE/ACM Trans Comput Biol Bioinform. 2019 Nov-Dec;16(6):1922-1935. doi: 10.1109/TCBB.2018.2844256. Epub 2018 Jun 5.
Protein complexes are crucial in improving our understanding of the mechanisms employed by proteins. Various computational algorithms have thus been proposed to detect protein complexes from protein interaction networks. However, given massive protein interactome data obtained by high-throughput technologies, existing algorithms, especially those with additionally consideration of biological information of proteins, either have low efficiency in performing their tasks or suffer from limited effectiveness. For addressing this issue, this work proposes to detect protein complexes from a protein interaction network with high efficiency and effectiveness. To do so, the original detection task is first formulated into an optimization problem according to the intuitive properties of protein complexes. After that, the framework of alternating direction method of multipliers is applied to decompose this optimization problem into several subtasks, which can be subsequently solved in a separate and parallel manner. An algorithm for implementing this solution is then developed. Experimental results on five large protein interaction networks demonstrated that compared to state-of-the-art protein complex detection algorithms, our algorithm outperformed them in terms of both effectiveness and efficiency. Moreover, as number of parallel processes increases, one can expect an even higher computational efficiency for the proposed algorithm with no compromise on effectiveness.
蛋白质复合物对于提高我们对蛋白质所采用的机制的理解至关重要。因此，已经提出了各种计算算法来从蛋白质相互作用网络中检测蛋白质复合物。然而，鉴于通过高通量技术获得的大量蛋白质互作组数据，现有的算法，特别是那些额外考虑蛋白质生物学信息的算法，要么在执行任务时效率低下，要么效果有限。为了解决这个问题，这项工作提出了一种高效、有效的从蛋白质相互作用网络中检测蛋白质复合物的方法。为此，首先根据蛋白质复合物的直观性质，将原始检测任务表示为一个优化问题。然后，应用交替方向乘子法将该优化问题分解为几个子任务，然后可以分别并行地解决这些子任务。最后，开发了一种实现该解决方案的算法。在五个大型蛋白质相互作用网络上的实验结果表明，与最先进的蛋白质复合物检测算法相比，我们的算法在有效性和效率方面都优于它们。此外，随着并行进程数量的增加，对于所提出的算法，在不影响有效性的情况下，可以预期更高的计算效率。
