Limits...
An efficient protein complex mining algorithm based on Multistage Kernel Extension.

Shen X, Zhao Y, Li Y, He T, Yang J, Hu X - BMC Bioinformatics (2014)

Bottom Line: 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.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.

View Article: PubMed Central - HTML - PubMed

ABSTRACT

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.

Show MeSH

Related in: MedlinePlus

Convert the undirected edge to directed and weighted edges. (a) is an interactive graph (undirected and unweighted graph) including node s  and node t .(b) shows the undirected and unweighted edge between node s  and node t . (c) shows the directed and weighted edges between node s  and node t  after conversion treatment.
© Copyright Policy - open-access
Related In: Results  -  Collection

License 1 - License 2
getmorefigures.php?uid=PMC4255745&req=5

Figure 1: Convert the undirected edge to directed and weighted edges. (a) is an interactive graph (undirected and unweighted graph) including node s and node t .(b) shows the undirected and unweighted edge between node s and node t . (c) shows the directed and weighted edges between node s and node t after conversion treatment.

Mentions: Where, is the number of the common nodes between node s and node t , is the number of common nodes between node t and node s . Since it is an undirected graph, . represents the degree of node s , and represents the degree of node t . After the conversion treatment, there are two directed and weighted edges between the node s and node t , as shown in Figure 1.


An efficient protein complex mining algorithm based on Multistage Kernel Extension.

Shen X, Zhao Y, Li Y, He T, Yang J, Hu X - BMC Bioinformatics (2014)

Convert the undirected edge to directed and weighted edges. (a) is an interactive graph (undirected and unweighted graph) including node s  and node t .(b) shows the undirected and unweighted edge between node s  and node t . (c) shows the directed and weighted edges between node s  and node t  after conversion treatment.
© Copyright Policy - open-access
Related In: Results  -  Collection

License 1 - License 2
Show All Figures
getmorefigures.php?uid=PMC4255745&req=5

Figure 1: Convert the undirected edge to directed and weighted edges. (a) is an interactive graph (undirected and unweighted graph) including node s and node t .(b) shows the undirected and unweighted edge between node s and node t . (c) shows the directed and weighted edges between node s and node t after conversion treatment.
Mentions: Where, is the number of the common nodes between node s and node t , is the number of common nodes between node t and node s . Since it is an undirected graph, . represents the degree of node s , and represents the degree of node t . After the conversion treatment, there are two directed and weighted edges between the node s and node t , as shown in Figure 1.

Bottom Line: 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.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.

View Article: PubMed Central - HTML - PubMed

ABSTRACT

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.

Show MeSH
Related in: MedlinePlus