Cargando…
An efficient protein complex mining algorithm based on Multistage Kernel Extension
BACKGROUND: In recent years, many protein complex mining algorithms, such as classical clique percolation (CPM) method and markov clustering (MCL) algorithm, have developed for protein-protein interaction network. However, most of the available algorithms primarily concentrate on mining dense protei...
Autores principales: | , , , , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
BioMed Central
2014
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4255745/ https://www.ncbi.nlm.nih.gov/pubmed/25474367 http://dx.doi.org/10.1186/1471-2105-15-S12-S7 |
_version_ | 1782347481786351616 |
---|---|
author | Shen, Xianjun Zhao, Yanli Li, Yanan He, Tingting Yang, Jincai Hu, Xiaohua |
author_facet | Shen, Xianjun Zhao, Yanli Li, Yanan He, Tingting Yang, Jincai Hu, Xiaohua |
author_sort | Shen, Xianjun |
collection | PubMed |
description | BACKGROUND: In recent years, many protein complex mining algorithms, such as classical clique percolation (CPM) method and markov clustering (MCL) algorithm, have developed for protein-protein interaction network. However, most of the available algorithms primarily concentrate on mining dense protein subgraphs as protein complexes, failing to take into account the inherent organizational structure within protein complexes. Thus, there is a critical need to study the possibility of mining protein complexes using the topological information hidden in edges. Moreover, the recent massive experimental analyses reveal that protein complexes have their own intrinsic organization. METHODS: Inspired by the formation process of cliques of the complex social network and the centrality-lethality rule, we propose a new protein complex mining algorithm called Multistage Kernel Extension (MKE) algorithm, integrating the idea of critical proteins recognition in the Protein- Protein Interaction (PPI) network,. MKE first recognizes the nodes with high degree as the first level kernel of protein complex, and then adds the weighted best neighbour node of the first level kernel into the current kernel to form the second level kernel of the protein complex. This process is repeated, extending the current kernel to form protein complex. In the end, overlapped protein complexes are merged to form the final protein complex set. RESULTS: Here MKE has better accuracy compared with the classical clique percolation method and markov clustering algorithm. MKE also performs better than the classical clique percolation method both on Gene Ontology semantic similarity and co-localization enrichment and can effectively identify protein complexes with biological significance in the PPI network. |
format | Online Article Text |
id | pubmed-4255745 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2014 |
publisher | BioMed Central |
record_format | MEDLINE/PubMed |
spelling | pubmed-42557452014-12-05 An efficient protein complex mining algorithm based on Multistage Kernel Extension Shen, Xianjun Zhao, Yanli Li, Yanan He, Tingting Yang, Jincai Hu, Xiaohua BMC Bioinformatics Research BACKGROUND: In recent years, many protein complex mining algorithms, such as classical clique percolation (CPM) method and markov clustering (MCL) algorithm, have developed for protein-protein interaction network. However, most of the available algorithms primarily concentrate on mining dense protein subgraphs as protein complexes, failing to take into account the inherent organizational structure within protein complexes. Thus, there is a critical need to study the possibility of mining protein complexes using the topological information hidden in edges. Moreover, the recent massive experimental analyses reveal that protein complexes have their own intrinsic organization. METHODS: Inspired by the formation process of cliques of the complex social network and the centrality-lethality rule, we propose a new protein complex mining algorithm called Multistage Kernel Extension (MKE) algorithm, integrating the idea of critical proteins recognition in the Protein- Protein Interaction (PPI) network,. MKE first recognizes the nodes with high degree as the first level kernel of protein complex, and then adds the weighted best neighbour node of the first level kernel into the current kernel to form the second level kernel of the protein complex. This process is repeated, extending the current kernel to form protein complex. In the end, overlapped protein complexes are merged to form the final protein complex set. RESULTS: Here MKE has better accuracy compared with the classical clique percolation method and markov clustering algorithm. MKE also performs better than the classical clique percolation method both on Gene Ontology semantic similarity and co-localization enrichment and can effectively identify protein complexes with biological significance in the PPI network. BioMed Central 2014-11-06 /pmc/articles/PMC4255745/ /pubmed/25474367 http://dx.doi.org/10.1186/1471-2105-15-S12-S7 Text en Copyright © 2014 Shen et al.; licensee BioMed Central Ltd. http://creativecommons.org/licenses/by/2.0 This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. The Creative Commons Public Domain Dedication waiver (http://creativecommons.org/publicdomain/zero/1.0/) applies to the data made available in this article, unless otherwise stated. |
spellingShingle | Research Shen, Xianjun Zhao, Yanli Li, Yanan He, Tingting Yang, Jincai Hu, Xiaohua An efficient protein complex mining algorithm based on Multistage Kernel Extension |
title | An efficient protein complex mining algorithm based on Multistage Kernel Extension |
title_full | An efficient protein complex mining algorithm based on Multistage Kernel Extension |
title_fullStr | An efficient protein complex mining algorithm based on Multistage Kernel Extension |
title_full_unstemmed | An efficient protein complex mining algorithm based on Multistage Kernel Extension |
title_short | An efficient protein complex mining algorithm based on Multistage Kernel Extension |
title_sort | efficient protein complex mining algorithm based on multistage kernel extension |
topic | Research |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4255745/ https://www.ncbi.nlm.nih.gov/pubmed/25474367 http://dx.doi.org/10.1186/1471-2105-15-S12-S7 |
work_keys_str_mv | AT shenxianjun anefficientproteincomplexminingalgorithmbasedonmultistagekernelextension AT zhaoyanli anefficientproteincomplexminingalgorithmbasedonmultistagekernelextension AT liyanan anefficientproteincomplexminingalgorithmbasedonmultistagekernelextension AT hetingting anefficientproteincomplexminingalgorithmbasedonmultistagekernelextension AT yangjincai anefficientproteincomplexminingalgorithmbasedonmultistagekernelextension AT huxiaohua anefficientproteincomplexminingalgorithmbasedonmultistagekernelextension AT shenxianjun efficientproteincomplexminingalgorithmbasedonmultistagekernelextension AT zhaoyanli efficientproteincomplexminingalgorithmbasedonmultistagekernelextension AT liyanan efficientproteincomplexminingalgorithmbasedonmultistagekernelextension AT hetingting efficientproteincomplexminingalgorithmbasedonmultistagekernelextension AT yangjincai efficientproteincomplexminingalgorithmbasedonmultistagekernelextension AT huxiaohua efficientproteincomplexminingalgorithmbasedonmultistagekernelextension |