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...

Descripción completa

Detalles Bibliográficos
Autores principales: Shen, Xianjun, Zhao, Yanli, Li, Yanan, He, Tingting, Yang, Jincai, Hu, Xiaohua
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