Limits...
MOfinder: a novel algorithm for detecting overlapping modules from protein-protein interaction network.

Yu Q, Li GH, Huang JF - J. Biomed. Biotechnol. (2012)

Bottom Line: We demonstrate that our method is more accurate than other 5 methods.Using the overlapping modules of human PPI network, we constructed the module-module communication network.Our study around overlapping modules suggests a new perspective on the analysis of PPI network and improves our understanding of disease.

View Article: PubMed Central - PubMed

Affiliation: State Key Laboratory of Genetic Resources and Evolution, Kunming Institute of Zoology, Chinese Academy of Sciences, Kunming 650223, China.

ABSTRACT
Since organism development and many critical cell biology processes are organized in modular patterns, many algorithms have been proposed to detect modules. In this study, a new method, MOfinder, was developed to detect overlapping modules in a protein-protein interaction (PPI) network. We demonstrate that our method is more accurate than other 5 methods. Then, we applied MOfinder to yeast and human PPI network and explored the overlapping information. Using the overlapping modules of human PPI network, we constructed the module-module communication network. Functional annotation showed that the immune-related and cancer-related proteins were always together and present in the same modules, which offer some clues for immune therapy for cancer. Our study around overlapping modules suggests a new perspective on the analysis of PPI network and improves our understanding of disease.

Show MeSH

Related in: MedlinePlus

© Copyright Policy - open-access
Related In: Results  -  Collection


getmorefigures.php?uid=PMC3303734&req=5

Mentions: MOfinder is based on an AMD (Approximate Minimum Degree Ordering) algorithm [35, 36] which has been used for network clustering from electrical engineering [37]. AMD algorithm is usually used in ordering a sparse matrix prior to Cholesky factorization (or for LU factorization with diagonal pivoting), and it can transform the sparse matrix to make the nonzero elements close to the diagonal. The approach used by MOfinder is summarized in Figure 1. MOfinder first converts the PPI file into a sparse matrix, where a nonzero element represents a protein-protein interaction. It then performs a global AMD of the sparse matrix in which the densely connected elements (module) will be clustered along the diagonal. Besides the global AMD, which produces the global ordering, a local AMD is performed to give the approximate minimum degree ordering. MOfinder uses a sliding window along the diagonal to fetch the local sparse matrix and make the local AMD. The clustering coefficient (CC) [38] value of the submatrix in the sliding window is calculated; if the CC value is not less than the cut-off, MOfinder will save the submatrix as a module. Then the sliding window moves one step along the diagonal to find new modules, and the iteration process is repeated until the sliding window reaches the end. Lastly, MOfinder removes redundant modules (if module A belongs to module B, A is removed) and saves results. The pseudocode of MOfinder algorithm is (see Algorithm 1).


MOfinder: a novel algorithm for detecting overlapping modules from protein-protein interaction network.

Yu Q, Li GH, Huang JF - J. Biomed. Biotechnol. (2012)

© Copyright Policy - open-access
Related In: Results  -  Collection

Show All Figures
getmorefigures.php?uid=PMC3303734&req=5

Mentions: MOfinder is based on an AMD (Approximate Minimum Degree Ordering) algorithm [35, 36] which has been used for network clustering from electrical engineering [37]. AMD algorithm is usually used in ordering a sparse matrix prior to Cholesky factorization (or for LU factorization with diagonal pivoting), and it can transform the sparse matrix to make the nonzero elements close to the diagonal. The approach used by MOfinder is summarized in Figure 1. MOfinder first converts the PPI file into a sparse matrix, where a nonzero element represents a protein-protein interaction. It then performs a global AMD of the sparse matrix in which the densely connected elements (module) will be clustered along the diagonal. Besides the global AMD, which produces the global ordering, a local AMD is performed to give the approximate minimum degree ordering. MOfinder uses a sliding window along the diagonal to fetch the local sparse matrix and make the local AMD. The clustering coefficient (CC) [38] value of the submatrix in the sliding window is calculated; if the CC value is not less than the cut-off, MOfinder will save the submatrix as a module. Then the sliding window moves one step along the diagonal to find new modules, and the iteration process is repeated until the sliding window reaches the end. Lastly, MOfinder removes redundant modules (if module A belongs to module B, A is removed) and saves results. The pseudocode of MOfinder algorithm is (see Algorithm 1).

Bottom Line: We demonstrate that our method is more accurate than other 5 methods.Using the overlapping modules of human PPI network, we constructed the module-module communication network.Our study around overlapping modules suggests a new perspective on the analysis of PPI network and improves our understanding of disease.

View Article: PubMed Central - PubMed

Affiliation: State Key Laboratory of Genetic Resources and Evolution, Kunming Institute of Zoology, Chinese Academy of Sciences, Kunming 650223, China.

ABSTRACT
Since organism development and many critical cell biology processes are organized in modular patterns, many algorithms have been proposed to detect modules. In this study, a new method, MOfinder, was developed to detect overlapping modules in a protein-protein interaction (PPI) network. We demonstrate that our method is more accurate than other 5 methods. Then, we applied MOfinder to yeast and human PPI network and explored the overlapping information. Using the overlapping modules of human PPI network, we constructed the module-module communication network. Functional annotation showed that the immune-related and cancer-related proteins were always together and present in the same modules, which offer some clues for immune therapy for cancer. Our study around overlapping modules suggests a new perspective on the analysis of PPI network and improves our understanding of disease.

Show MeSH
Related in: MedlinePlus