article

Identification of protein complexes using weighted pagerank-nibble algorithm and core-attachment structure

Editor: Ying Xu Authors:

Lusheng WangAuthors Info & Claims

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), Volume 12, Issue 1

Pages 179 - 192

https://doi.org/10.1109/TCBB.2014.2343954

Published: 01 January 2015 Publication History

Abstract

Protein complexes play a significant role in understanding the underlying mechanism of most cellular functions. Recently, many researchers have explored computational methods to identify protein complexes from protein-protein interaction (PPI) networks. One group of researchers focus on detecting local dense subgraphs which correspond to protein complexes by considering local neighbors. The drawback of this kind of approach is that the global information of the networks is ignored. Some methods such as Markov Clustering algorithm (MCL), PageRank-Nibble are proposed to find protein complexes based on random walk technique which can exploit the global structure of networks. However, these methods ignore the inherent core-attachment structure of protein complexes and treat adjacent node equally. In this paper, we design a weighted PageRank-Nibble algorithm which assigns each adjacent node with different probability, and propose a novel method named WPNCA to detect protein complex from PPI networks by using weighted PageRank-Nibble algorithm and core-attachment structure. Firstly, WPNCA partitions the PPI networks into multiple dense clusters by using weighted PageRank-Nibble algorithm. Then the cores of these clusters are detected and the rest of proteins in the clusters will be selected as attachments to form the final predicted protein complexes. The experiments on yeast data show that WPNCA outperforms the existing methods in terms of both accuracy and p-value. The software for WPNCA is available at "http://netlab.csu.edu.cn/bioinfomatics/weipeng/WPNCA/download.html"

References

[1]

G. Rigaut, A. Shevchenko, B. Rutz, M. Wilm, M. Mann, and B. Séraphin, "A generic protein purification method for protein complex characterization and proteome exploration," Nature Biotechnol., vol. 17, no. 10, pp. 1030-1032, 1999.

[2]

T. Ito, T. Chiba, R. Ozawa, M. Yoshida, M. Hattori, and Y. Sakaki, "A comprehensive two-hybrid analysis to explore the yeast protein interactome," Proc. Nat. Acad. Sci., vol. 98, no. 8, pp. 4569-4574, 2001.

[3]

J. Wang, X. Peng, W. Peng, and F.-X. Wu, "Dynamic protein interaction network construction and applications," Proteomics, vol. 14, no. 4/5, pp. 338-352, 2014.

[4]

A. H. Y. Tong, B. Drees, G. Nardelli, G. D. Bader, B. Brannetti, L. Castagnoli, M. Evangelista, S. Ferracuti, B. Nelson, S. Paoluzi, M. Quondam, A. Zucconi, C. W. V. Hogue, S. Fields, C. Boone, and G. Cesareni, "A combined experimental and computational strategy to define protein interaction networks for peptide recognition modules," Sci. Signal., vol. 295, no. 5553, pp. 321-324, 2002.

[5]

R. Karp, "Reducibility among combinatorial problems," 50 Years of Integer Programming 1958-2008, pp. 219-241, 2010.

[6]

M. Girvan and M. Newman, "Community structure in social and biological networks," Proc. Nat. Acad. Sci., vol. 99, no. 12, pp. 7821-7826, 2002.

[7]

S. van Dongen, "Graph clustering by flow simulation," PhD dissertation, Univ. Utrecht, Utrecht, The Netherlands, 2000.

[8]

A. Enright, S. Van Dongen, and C. Ouzounis, "An efficient algorithm for large-scale detection of protein families," Nucleic Acids Res., vol. 30, no. 7, pp. 1575-1584, 2002.

[9]

X. Li, M. Wu, C. Kwoh, and S. Ng, "Computational approaches for detecting protein complexes from protein interaction networks: A survey," BMC Genomics, vol. 11, no. 1, p. S3, 2010.

[10]

S. Srihari, K. Ning, and H. Leong, "MCL-CAW: A refinement of MCL for detecting yeast complexes from weighted PPI networks by incorporating core-attachment structure," BMC Bioinformat., vol. 11, no. 1, p. 504, 2010.

[11]

G. Liu, L. Wong, and H. Chua, "Complex discovery from weighted PPI networks," Bioinformatics, vol. 25, no. 15, pp. 1891-1897, 2009.

[12]

B. Adamcsek, G. Palla, I. Farkas, I. Derényi, and T. Vicsek, "Cfinder: Locating cliques and overlapping modules in biological networks," Bioinformatics, vol. 22, no. 8, pp. 1021-1023, 2006.

[13]

G. Palla, I. Dernyi, I. Farkas, and T. Vicsek, "Uncovering the overlapping community structure of complex networks in nature and society," Nature, vol. 435, no. 7043, pp. 814-818, 2005.

[14]

G. Bader and C. Hogue, "An automated method for finding molecular complexes in large protein interaction networks," BMC Bioinformat., vol. 4, no. 1, p. 2, 2003.

[15]

M. Altaf-Ul-Amin, Y. Shinbo, K. Mihara, K. Kurokawa, and S. Kanaya, "Development and implementation of an algorithm for detection of protein complexes in large interaction networks," BMC Bioinformat., vol. 7, no. 1, p. 207, 2006.

[16]

M. Li, J. Chen, J. Wang, B. Hu, and G. Chen, "Modifying the DPClus algorithm for identifying protein complexes based on new topological structures," BMC Bioinformat., vol. 9, no. 1, p. 398, 2008.

[17]

J. Wang, M. Li, J. Chen, and Y. Pan, "A fast hierarchical clustering algorithm for functional modules discovery in protein interaction networks," IEEE/ACM Trans. Comput. Biol. Bioinformat., vol. 8, no. 3, pp. 607-620, 2011.

[18]

P. Jiang and M. Singh, "SPICi: A fast clustering algorithm for large biological networks," Bioinformatics, vol. 26, no. 8, pp. 1105-1111, 2010.

[19]

T. Nepusz, H. Yu, and A. Paccanaro, "Detecting overlapping protein complexes in protein-protein interaction networks," Nature Methods, vol. 9, no. 5, pp. 471-472, 2012.

[20]

A. Gavin, P. Aloy, P. Grandi, R. Krause, M. Boesche, M. Marzioch, C. Rau, L. J. Jensen, S. Bastuck, B. Dümpelfeld, A. Edelmann, M.-A. Heurtier, V. Hoffman, C. Hoefert, K. Klein, M. Hudak, A.-M. Michon, M. Schelder, M. Schirle, M. Remor, T. Rudi, S. Hooper, A. Bauer, T. Bouwmeester, G. Casari, G. Drewes, G. Neubauer, J. M. Rick, B. Kuster, P. Bork, R. B. Russell, and G. Superti-Furga, "Proteome survey reveals modularity of the yeast cell machinery," Nature, vol. 440, no. 7084, pp. 631-636, 2006.

[21]

H. Leung, Q. Xiang, S. Yiu, and F. Chin, "Predicting protein complexes from PPI data: A core-attachment approach," J. Comput. Biol., vol. 16, no. 2, pp. 133-144, 2009.

[22]

M. Wu, X. Li, C. Kwoh, and S. Ng, "A core-attachment based method to detect protein complexes in PPI networks," BMC Bioinformat., vol. 10, no. 1, p. 169, 2009.

[23]

B. Zhao, J. Wang, M. Li, F. Wu, and Y. Pan, "Detecting protein complexes based on uncertain graph model," IEEE/ACM Trans. Comput. Biol. Bioinformat., vol. 11, no. 3, pp. 486-497, 2014.

[24]

R. Andersen, F. Chung, and K. Lang, "Using PageRank to locally partition a graph," Internet Math., vol. 4, no. 1, pp. 35-64, 2007.

[25]

J. Leskovec, K. Lang, A. Dasgupta, and M. Mahoney, "Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters," Internet Math., vol. 6, no. 1, pp. 29-123, 2009.

[26]

K. Voevodski, S. Teng, and Y. Xia, "Finding local communities in protein networks," BMC Bioinformat., vol. 10, no. 1, p. 297, 2009.

[27]

L. Hodgkinson, and R. Karp, "Algorithms to detect multiprotein modularity conserved during evolution," IEEE/ACM Trans. Comput. Biol. Bioinformat., vol. 9, no. 4, pp. 1046-1058, 2012.

[28]

J. Wang, M. Li, H. Wang, and Y. Pan, "Identification of essential proteins based on edge clustering coefficient," IEEE/ACM Trans. Comput. Biol. Bioinformat., vol. 9, no. 4, pp. 1070-1080, 2012.

[29]

X. Tang, J. Wang, J. Zhong, and Y. Pan, "Predicting essential proteins based on weighted degree centrality," IEEE/ACM Trans. Comput. Biol. Bioinformat., vol. 11, no. 2, pp. 407-418, 2014.

[30]

M. Li, R. Zheng, H. Zhang, J. Wang, and Y. Pan, "Effective identification of essential proteins based on priori knowledge, network topology and gene expressions," Methods, vol. 67, pp. 325-333, 2014.

[31]

K. Macropol, T. Can, and A. Singh, "RRW: Repeated random walks on genome-scale protein networks for local cluster discovery," BMC Bioinformat., vol. 10, no. 1, p. 283, 2009.

[32]

I. Xenarios, L. Salwinski, X. Duan, P. Higney, S. Kim, and D. Eisenberg, "DIP, the database of interacting proteins: A research tool for studying cellular networks of protein interactions," Nucleic Acids Res., vol. 30, no. 1, pp. 303-305, 2002.

[33]

M. Li, J. Wang, X. Chen, H. Wang, and Y. Pan, "A local average connectivity-based method for identifying essential proteins from the network level," Comput. Biol. Chem., vol. 35, no. 3, pp. 143-150, 2011.

[34]

S. Pu, J. Wong, B. Turner, E. Cho, and S. Wodak, "Up-to-date catalogues of yeast protein complexes," Nucleic Acids Res., vol. 37, no. 3, pp. 825-831, 2009.

[35]

E. Boyle, S. Weng, J. Gollub, H. Jin, D. Botstein, J. Cherry, and G. Sherlock, "Go::TermFinder--Open source software for accessing gene ontology information and finding significantly enriched gene ontology terms associated with a list of genes," Bioinformatics, vol. 20, no. 18, pp. 3710-3715, 2004.

[36]

P. A. Grant, D. Schieltz, M. G. Pray-Grant, D. J. Steger, J. C. Reese, J. R. Yates III, and J. L. Workman, "A subset of TAF(II)s are integral components of the saga complex required for nucleosome acetylation and transcriptional stimulation." Cell, vol. 94, no. 1, pp. 45-53, 1998.

Cited By

Zhang XZhao STang YXia XWang WBaysal OLinares-Vasquez MMoran KSteinmacher I(2024)OpenGalaxy: An interactive exploration platform for a visualized GitHub Full Domain collaboration networkProceedings of the 32nd IEEE/ACM International Conference on Program Comprehension10.1145/3643916.3644441(455-459)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1145/3643916.3644441
Chang YMa HChang LLi Z(2022)Community detection with attributed random walk via seed replacementFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-021-0482-x16:5Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s11704-021-0482-x
Meng XLi WPeng XLi YLi M(2021)Protein interaction networks: centrality, modularity, dynamics, and applicationsFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-020-8179-015:6Online publication date: 1-Dec-2021
https://dl.acm.org/doi/10.1007/s11704-020-8179-0
Show More Cited By

Index Terms

Identification of protein complexes using weighted pagerank-nibble algorithm and core-attachment structure

Recommendations

Identification of protein complexes by comparative analysis of yeast and bacterial protein interaction data
RECOMB '04: Proceedings of the eighth annual international conference on Research in computational molecular biology

Mounting evidence shows that many protein complexes are conserved in evolution. Here we use conservation to find complexes that are common to yeast S. Cerevisiae and bacteria H. pylori. Our analysis combines protein interaction data, that are available ...
A cell-core-attachment approach for identifying protein complexes in yeast protein-protein interaction network
ICNC-FSKD 2015

With the increasing of available protein-protein interaction (PPI) data, many computational methods have been explored to identify protein complexes from PPI networks. Majority of algorithms employ the feature of local neighbors to detect local dense ...
Detecting protein complexes from noisy protein interaction data
BIOKDD '12: Proceedings of the 11th International Workshop on Data Mining in Bioinformatics

High-throughput experimental techniques have made available large datasets of experimentally detected protein-protein interactions. However, experimentally determined protein complexes datasets are not exhaustive nor reliable. A protein complex plays a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 01 January 2015

Accepted: 16 July 2014

Revised: 02 April 2014

Received: 17 February 2013

Published in TCBB Volume 12, Issue 1

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
143
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang XZhao STang YXia XWang WBaysal OLinares-Vasquez MMoran KSteinmacher I(2024)OpenGalaxy: An interactive exploration platform for a visualized GitHub Full Domain collaboration networkProceedings of the 32nd IEEE/ACM International Conference on Program Comprehension10.1145/3643916.3644441(455-459)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1145/3643916.3644441
Chang YMa HChang LLi Z(2022)Community detection with attributed random walk via seed replacementFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-021-0482-x16:5Online publication date: 1-Oct-2022
https://dl.acm.org/doi/10.1007/s11704-021-0482-x
Meng XLi WPeng XLi YLi M(2021)Protein interaction networks: centrality, modularity, dynamics, and applicationsFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-020-8179-015:6Online publication date: 1-Dec-2021
https://dl.acm.org/doi/10.1007/s11704-020-8179-0
Lugo-Martinez JDengjel JBar-Joseph ZMurphy RShi XBuck MMa JVeltri P(2019)Integration of Heterogeneous Experimental Data Improves Global Map of Human Protein ComplexesProceedings of the 10th ACM International Conference on Bioinformatics, Computational Biology and Health Informatics10.1145/3307339.3342150(144-153)Online publication date: 4-Sep-2019
https://dl.acm.org/doi/10.1145/3307339.3342150
He TChan K(2018)Evolutionary Graph Clustering for Protein Complex IdentificationIEEE/ACM Transactions on Computational Biology and Bioinformatics10.1109/TCBB.2016.264210715:3(892-904)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1109/TCBB.2016.2642107
Zhu XQiu JXie MWang J(2017)A multi-objective biclustering algorithm based on fuzzy mathematicsNeurocomputing10.1016/j.neucom.2017.01.095253:C(177-182)Online publication date: 30-Aug-2017
https://dl.acm.org/doi/10.1016/j.neucom.2017.01.095
Shafin MKabir KRidwan IAnannya TKarim RHoque MRahman M(2015)Impact of heuristics in clustering large biological networksComputational Biology and Chemistry10.1016/j.compbiolchem.2015.05.00759:PA(28-36)Online publication date: 1-Dec-2015
https://dl.acm.org/doi/10.1016/j.compbiolchem.2015.05.007

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents