An Agglomerate Algorithm for Mining Overlapping and Hierarchical Functional Modules in Protein Interaction Networks

作者：Ren Jun^*; Wang Jianxin; Chen Jianaer; Li Min; Chen Gang

来源：6th International Symposium on Bioinformatics Research and Applications, 2010-05-23 to 2010-05-26.

• overlapping functional module
• hierarchical module structure
• agglomerative algorithm

Real PPI networks commonly have large size. Functional modules in them are usually overlapping and hierarchical. So it is significant to identify both overlapping and hierarchical modules with low time complexity. However previous methods can not do it. A new agglomerative algorithm, MOMA, is proposed in the paper to resolve this problem. MOMA classifies subgraphs into clusters and vertices. Clusters can overlap each other. MOMA identifies overlapping and hierarchical functional modules by merging overlapping subgraphs. Its time complexity is O(N(2)). We apply MOMA, G-N algorithm and Cfinder on the yeast core PPI network. Comparing with G-N algorithm, MOMA can identify overlapping modules. Comparing with Cfinder, MOMA can identify hierarchical modules. Distributions of the lowest P-value show that the module set identified by MOMA has the stronger biological significance than those identified by the other two algorithms.

• 出版日期2010
• 单位中南大学