article

Detecting protein complexes based on uncertain graph model

Editor: Ying Xu Authors:

Yi PanAuthors Info & Claims

IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), Volume 11, Issue 3

Pages 486 - 497

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

Published: 01 May 2014 Publication History

Abstract

Advanced biological technologies are producing large-scale protein-protein interaction (PPI) data at an ever increasing pace, which enable us to identify protein complexes from PPI networks. Pair-wise protein interactions can be modeled as a graph, where vertices represent proteins and edges represent PPIs. However most of current algorithms detect protein complexes based on deterministic graphs, whose edges are either present or absent. Neighboring information is neglected in these methods. Based on the uncertain graph model, we propose the concept of expected density to assess the density degree of a subgraph, the concept of relative degree to describe the relationship between a protein and a subgraph in a PPI network. We develop an algorithm called DCU (detecting complex based on uncertain graph model) to detect complexes from PPI networks. In our method, the expected density combined with the relative degree is used to determine whether a subgraph represents a complex with high cohesion and low coupling. We apply our method and the existing competing algorithms to two yeast PPI networks. Experimental results indicate that our method performs significantly better than the state-of-the-art methods and the proposed model can provide more insights for future study in PPI networks.

References

[1]

T. Ito et al., "A Comprehensive Two-Hybrid Analysis to Explore the Yeast Protein Interactome," Proc. Nat'l Aademy of Sciences USA, vol. 98, no. 8, pp. 4569-4574, Apr. 2001.

[2]

G. Rigaut et al., "A Generic Protein Purification Method for Protein Complex Characterization and Proteome Exploration," Nature Biotechnol., vol. 17, pp. 1030-1032, Oct. 1999.

[3]

Y. Ho et al., "Systematic Identification of Protein Complexes in Saccharomyces Cerevisiae by Mass Spectrometry," Nature, vol. 405, pp. 180-183, Jan. 2002.

[4]

G.D. Bader and C.W. Hogue, "An Automated Method for Finding Molecular Complexes in Large Protein Interaction Networks," BMC Bioinformatics, vol. 4, article 2, 2003.

[5]

A.J. Enright, S.V. Dongen, and C.A. Ouzounis, "An Efficient Algorithm for Large-Scale Detection of Protein Families," Nucleic Acids Research, vol. 30, no. 7, pp. 1575-1584, 2002.

[6]

G. Palla et al., "Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society," Nature, vol. 435, pp. 814-818, 2005.

[7]

B. Adamcsek et al., "CFinder: Locating Cliques and Overlapping Modules in Biological Networks," Bioinformatics, vol. 22, no. 8, pp. 1021-1023, 2006.

[8]

G. Liu, L. Wong, and H.N. Chua, "Complex Discovery from Weighted PPI Networks," Bioinformatics, vol. 25, no. 15, pp. 1891- 1897, 2009.

[9]

P. Jiang and M. Singh, "SPICi: A Fast Clustering Algorithm for Large Biological Networks," Bioinformatics, vol. 26, no. 8, pp. 1105- 1111, 2010.

[10]

J.X. Wang et al., "A Fast Hierarchical Clustering Algorithm for Functional Modules Discovery in Protein Interaction Networks," IEEE/ACM Trans. Computational Biology and Bioinformatics, vol. 8, no. 3, pp. 607-620, 2011.

[11]

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, May 2012.

[12]

X.J. Ding et al., "Mining Protein Complexes from PPI Networks Using the Minimum Vertex Cut," Tsinghua Science and Technology, vol. 17, no. 6, pp. 674-681, 2012.

[13]

A.C. Gavin et al., "Proteome Survey Reveals Modularity of the Yeast Cell Machinery," Genome Research, vol. 440, pp. 631-636, 2006.

[14]

Z. Dezso, Z.D. Oltvai, and A.L. Barabasi, "Bioinformatics Analysis of Experimentally Determined Protein Complexes in the Yeast Saccharomyces Cerevisiae," Genome Research, vol. 13, pp. 2450- 2454, 2003.

[15]

M. Wu et al., "A Core-Attachment Based Method to Detect Protein Complexes in PPI Networks," BMC Bioinformatics, vol. 10, article 169, 2009.

[16]

H.C. Leung et al., "Predicting Protein Complexes from PPI Data: A Core-Attachment Approach," J. Computational Biology, vol. 16, no. 2, pp. 133-144, 2009.

[17]

X. Ma and L. Gao, "Predicting Protein Complexes in Protein Interaction Networks Using a Core-Attachment Algorithm Based on Graph Communicability," Information Sciences, vol. 189, pp. 233- 254, 2012.

[18]

X. Ma and L. Gao, "Discovering Protein Complexes in Protein Interaction Networks via Exploring the Weak Ties Effect," BMC Systems Biology, vol. 6, article 1, 2012.

[19]

M. Li et al., "Effective Identification of Essential Proteins Based on Priori Knowledge, Network Topology and Gene Expressions," Methods. 2014.

[20]

C.V. Mering et al., "Comparative Assessment of Large-Scale Data Sets of Protein-Protein Interactions," Nature, vol. 417, pp. 399-403, May 2002.

[21]

S. Tsoka and C.A. Ouzounis, "Prediction of Protein Interactions: Metabolic Enzymes are Frequently Involved in Gene Fusion," Nature Genetics, vol. 26, pp. 141-142, 2000.

[22]

R. Lisa et al., "Identification of Potential Interaction Networks Using Sequence-Based Searches for Conserved Protein-Protein Interactions or 'Interologs'," Genome Research, vol. 11, pp. 2120- 2126, 2001.

[23]

X. Tang et al., "Predicting Essential Proteins Based on Weighted Degree Centrality," IEEE/ACM Transactions on Computational Biology and Bioinformatics, preprint, 19 Dec. 2013.

[24]

M. Strong et al., "Inference of Protein Function and Protein Linkages in Mycobaterium Tuberculosis Based on Prokaryotic Genome Organization: A Combined Computational Approach," Genome Biology, vol. 4, article 59, 2003.

[25]

S.V. Date and E.M. Marcotte, "Discovery of Uncharacterized Cellular Systems by Genome-Wide Analysis of Functional Linkages," Nature Biotechnology, vol. 21, no. 9, pp. 296-305, 2001.

[26]

T. Yamada, M. Kanehisa, and S. Goto, "Extraction of Phylogenetic Network Modules from the Metabolic Network," BMC Bioinformatics, vol. 7, article 130, 2006.

[27]

J. Wu, S. Kasif, and C. DeLisi, "Identification of Functional Links between Genes Using Phylogenetic Profiles," Bioinformatics, vol. 19, no. 12, pp. 1524-1530, 2003.

[28]

J.R. Bock and D.A. Gough, "Predicting Protein-Protein Interactions from Primary Structure," Bioinformatics, vol. 17, no. 5, pp. 455-460, 2001.

[29]

I. Albert and R. Albert, "Conserved Network Motifs Allow Protein-Protein Interaction Prediction," Bioinformatics, vol. 20, no. 18, pp. 3346-3352, 2004.

[30]

J.R. Bock and D.A. Gough, "Whole-Proteome Interactioin Mining," Bioinformatics, vol. 19, no. 1, pp. 125-135, 2003.

[31]

S.L. Lo et al., "Effect of Training Datasets on Support Vector Machine Prediction of Protein-Protein Interactions," Proteomics, vol. 5, no. 4, pp. 876-884, Mar. 2005.

[32]

C.M. Deane et al., "Protein Interactions: Two Methods for Assessment of the Reliability of High Throughput Observations," Molecular and Cellular Proteomics, vol. 1, no. 5, pp. 349-356, 2002.

[33]

M. Deng et al., "Assessment of the Reliability of Protein-Protein Interactions and Protein Function Prediction," Proc. Pacific Symp. Biocomputing Hawaii, pp. 140-151, 2003.

[34]

P. D'haeseleer and G.M. Church, "Estimating and Improving Protein Interaction Error Rates," Proc. IEEE Computational Systems Bioinformatics Conf. USA, pp. 216-223, 2004.

[35]

M.A. Gilchrist et al., "A Statistical Framework for Combining and Interpreting Proteomic Datasets," Bioinformatics, vol. 20, no. 5, pp. 689-700, 2004.

[36]

V.C. Mering et al., "Comparative Assessment of Large-Scale Data Sets of Protein-Protein Interactions," Nature, vol. 417, pp. 399-403, May 2002.

[37]

A. Zhou et al., "A Survey on the Management of Uncertain Data," Chinese J. Computers, vol. 32, no. 1, pp. 1-16, 2009.

[38]

L. Wei and L. Chen, "Community Detection in Disease-Gene Network Based on Principal Component Analysis," Tsinghua Science and Technology, vol. 18, no. 5, pp. 454-461, 2013.

[39]

Y. Ye, L. Chen, and G. Wang, "Efficiently Answering Probability Threshold-Based Shortest Path Queries over Uncertain Graphs," Proc. 15th Int'l Conf. Database Systems for Advanced Applications (DASFAA '10), 2010.

[40]

R.M. Jin, L. Liu, and C. Aggarwal, "Discovering Highly Reliable Subgraphs in Uncertain Graphs," Proc. 17th ACM SIGKDD Int'l Conf. Knowledge Discovery and Data Mining (KDD '11), vol. 11, 2011.

[41]

X.L. Li, C.S. Foo, and S.K. Ng, "Discovering Protein Complexes in Dense Reliable Neighborhoods of Protein Interaction Networks," Proc. Computational Systems Bioinformatics Conf., pp. 157-168, 2007.

[42]

Y. Zhang et al., "Co-regulated Protein Functional Modules with Varying Activities in Dynamic PPI Networks," Tsinghua Science and Technology, vol. 18, no. 5, pp. 530-540, 2013.

[43]

X. Xenarios et al., "DIP: The Database of Interacting Proteins," Nucleic Acids Research, vol. 28, no. 1, pp. 289-291, 2000.

[44]

N.J. Krogan et al., "Global Landscape of Protein Complexes in the Yeast Saccharomyces Cerevisiae," Nature, vol. 440, pp. 637-643, Mar. 2006.

[45]

S. Pu et al., "Up-to-Date Catalogues of Yeast Protein Complexes," Nucleic Acids Research, vol. 37, no. 3, pp. 825-831, 2009.

[46]

Z.P. Xie et al., "Construction of Co-Complex Score Matrix for Protein Complex Prediction from AP-MS Data," Bioinformatics, vol. 27, pp. 159-166, 2011.

[47]

M.A. Harris et al., "The Gene Ontology (GO) Database and Informatics Resource," Nucleic Acids Research, vol. 32, pp. D258-D261, 2004.

[48]

M. Li et al., "hF-Measure: A New Measurement for Evaluating Clusters in Protein-Protein Interaction Networks," Proteomics, vol. 13, pp. 291-300, 2013.

[49]

S.R. Navarro et al., "Sus1, a Functional Component of the SAGA Histone Acetylase Complex and the Nuclear Pore-Associated mRNA Export Machinery," Cell, vol. 116, pp. 75-86, 2004.

[50]

H.W. Mewes et al., "MIPS: Analysis and Annotation of Proteins from Whole Genomes," Nucleic Acids Research, vol. 32, pp. 41-44, 2004.

[51]

S. Paul et al., "Cytoscape: A Software Environment for Integrated Models of Biomolecular Interaction Networks," Genome Research, vol. 13, no. 11, pp. 2498-2504, 2003.

Cited By

Lee ENoh SSeo J(2023)SageProceedings of the VLDB Endowment10.14778/3565838.356584415:13(3897-3910)Online publication date: 20-Jan-2023
https://dl.acm.org/doi/10.14778/3565838.3565844
Zhou AWang YChen L(2023)Butterfly counting and bitruss decomposition on uncertain bipartite graphsThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-023-00782-432:5(1013-1036)Online publication date: 17-Feb-2023
https://dl.acm.org/doi/10.1007/s00778-023-00782-4
Banerjee S(2022)A survey on mining and analysis of uncertain graphsKnowledge and Information Systems10.1007/s10115-022-01681-w64:7(1653-1689)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1007/s10115-022-01681-w
Show More Cited By

Index Terms

Detecting protein complexes based on uncertain graph model

Recommendations

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 ...
Spectral clustering for detecting protein complexes in protein-protein interaction (PPI) networks

In this paper, we study spectral clustering for detecting protein complexes in PPI (protein-protein interaction) networks, focusing on two open issues: (i) constructing similarity graphs; and (ii) determining the number of clusters. First, we study four ...
A partially shared joint clustering framework for detecting protein complexes from multiple state-specific signed interaction networks
Abstract
Detecting protein complexes is critical for studying cellular organizations and functions. The accumulation of protein–protein interaction (PPI) data enables the identification of protein complexes computationally. Although a great ...
Highlights
- A novel partially shared singed network clustering (PS-SNC) model is proposed for joint clustering of multiple signed protein-protein interaction (PPI) ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Computational Biology and Bioinformatics

IEEE/ACM Transactions on Computational Biology and Bioinformatics Volume 11, Issue 3

May/June 2014

159 pages

ISSN:1545-5963

Editor:
Ying Xu

Issue’s Table of Contents

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 01 May 2014

Accepted: 27 December 2013

Revised: 23 December 2013

Received: 02 July 2013

Published in TCBB Volume 11, Issue 3

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
276
Total Downloads

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

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lee ENoh SSeo J(2023)SageProceedings of the VLDB Endowment10.14778/3565838.356584415:13(3897-3910)Online publication date: 20-Jan-2023
https://dl.acm.org/doi/10.14778/3565838.3565844
Zhou AWang YChen L(2023)Butterfly counting and bitruss decomposition on uncertain bipartite graphsThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-023-00782-432:5(1013-1036)Online publication date: 17-Feb-2023
https://dl.acm.org/doi/10.1007/s00778-023-00782-4
Banerjee S(2022)A survey on mining and analysis of uncertain graphsKnowledge and Information Systems10.1007/s10115-022-01681-w64:7(1653-1689)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1007/s10115-022-01681-w
Hussain SButt IHanif MAnwar S(2022)Clustering uncertain graphs using ant colony optimization (ACO)Neural Computing and Applications10.1007/s00521-022-07063-134:14(11721-11738)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1007/s00521-022-07063-1
Zhou AWang YChen L(2021)Butterfly counting on uncertain bipartite graphsProceedings of the VLDB Endowment10.14778/3489496.348950215:2(211-223)Online publication date: 1-Oct-2021
https://dl.acm.org/doi/10.14778/3489496.3489502
Cao J(2021)Design and Implementation of Human-Computer Interaction System in Parallel Digital Library System Based on Neural NetworkScientific Programming10.1155/2021/99215512021Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1155/2021/9921551
Gu LHan YWang CChen WJiao JYuan X(2019)RETRACTED ARTICLE: Module overlapping structure detection in PPI using an improved link similarity-based Markov clustering algorithmNeural Computing and Applications10.1007/s00521-018-3508-z31:5(1481-1490)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1007/s00521-018-3508-z
(2018)A framework for identifying functional modules in dynamic networksInternational Journal of Data Mining and Bioinformatics10.5555/3292787.329278821:1(1-17)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.5555/3292787.3292788
(2018)A framework for identifying functional modules in dynamic networksInternational Journal of Data Mining and Bioinformatics10.5555/3292781.329278221:1(1-17)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.5555/3292781.3292782
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
Show More Cited By

View Options

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