Mining Functional Modules in Uncertain Protein-Protein Interaction Network

Abstract:

Mining functional modules with biological significance has attracted lots of attention recently. However, protein-protein interaction (PPI) network and other biological data generally bear uncertainties attributed to noise, incompleteness and inaccuracy in practice. In this paper, we focus on received PPI data with uncertainties to explore interesting protein complexes. Moreover, some novel conceptions extended from known graph conceptions are used to develop a depth-first algorithm to mine protein complexes in a simple uncertain graph. Our experiments take protein complexes from MIPS database as standard of accessing experimental results. Experiment results indicate that our algorithm has good performance in terms of coverage and precision. Experimental results are also assessed on Gene Ontology (GO) annotation, and the evaluation demonstrates proteins of our most acquired protein complexes show a high similarity. Finally, several experiments are taken to test the scalability of our algorithm. The result is also observed.

• Periodical: Applied Mechanics and Materials (Volumes 135-136)
• Pages: 602-608
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.135-136.602
• Online since: October 2011
• Authors: Ya Meng, Xue Qun Shang, Miao Miao, Miao Wang
• Keywords: Expected Density, Functional Module, PPI, Relativity, Uncertain Graph

References

[1] King A D, Przulj N, Jurisica I. Protein complex prediction via cost-based clustering [J]. Bioinformatics, 2004, 20(17): 3013-3020.

DOI: 10.1093/bioinformatics/bth351

[2] Girvan M, Newman M. Community structure in social and biological networks [J]. PNAS, 2002, 99: 7821-7826.

[3] Lou F, Yang Y, Chin-Fu Chen, Chang R, Zhou J and Richard HS. Modular organization of protein interaction networks [J]. Bioinformatics, 2007, 23(2): 207-214.

[4] Zou Z, L J, Gao H and Zhang S. Frequent subgraph pattern mining on uncertain graph data. IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, VOL. 22, 2010: 583-592.

DOI: 10.1109/tkde.2010.80

[5] Charu CA, Li Y, Wang J Y, Wang J. Frequent Pattern Mining with Uncertain Data. ACM, 2009: 29-37.

[6] Yan X, Zhou Xand Han J. Mining closed relational graphs with connectivity Constraints. ACM, 2005: 324-333.

[7] Yan X, Han J. Closegraph: Mining closed frequent graph patterns. ACM, 2003: 286-295.

DOI: 10.1145/956750.956784

[8] Huan J, Wang W, Prins J, Yang J. Spin: Mining maximal frequent sub-graphs from graph databases. ACM, 2004: 581-586.

DOI: 10.1145/1014052.1014123

[9] Zou Z, L J, Gao H and Zhang S. Finding Top-k Maximal Cliques in an Uncertain Graph. IEEE, 2010: 649-652.

[10] Nevan JK, Gerard C, Yu H, Zhong G, Guo X and Alexandx l et al. Global landscape of protein complexes in the yeast Saccharomy cescerevisiae. Nature, 2006: 637-643.