Clustering PPI Data Based on Ant Colony Optimization Algorithm

LEI Xiujuan; WU Shuang; GE Liang; ZHANG Aidong

Article Contents

Article Navigation > Chinese Journal of Electronics > 2013 > 22(1): 118-123

LEI Xiujuan, WU Shuang, GE Liang, ZHANG Aidong. Clustering PPI Data Based on Ant Colony Optimization Algorithm[J]. Chinese Journal of Electronics, 2013, 22(1): 118-123.

Citation:

LEI Xiujuan, WU Shuang, GE Liang, ZHANG Aidong. Clustering PPI Data Based on Ant Colony Optimization Algorithm[J]. Chinese Journal of Electronics, 2013, 22(1): 118-123.

LEI Xiujuan, WU Shuang, GE Liang, ZHANG Aidong. Clustering PPI Data Based on Ant Colony Optimization Algorithm[J]. Chinese Journal of Electronics, 2013, 22(1): 118-123.

Citation:

LEI Xiujuan, WU Shuang, GE Liang, ZHANG Aidong. Clustering PPI Data Based on Ant Colony Optimization Algorithm[J]. Chinese Journal of Electronics, 2013, 22(1): 118-123.

PDF( 292 KB)

Clustering PPI Data Based on Ant Colony Optimization Algorithm

1.
College of Computer Science, Shaanxi Normal University, Xi’an 710062, China;
2.
Department of Computer Science and Engineering, State University of New York at Buffalo, USA

Funds: This work is supported by the National Natural Science Foundation of China (No.61100164, No.61173190), the Natural Science Foundation of Shaanxi Province of China (No.2010JQ8034), the Fundamental Research Funds for the Central Universities in Shaanxi Normal University (No.GK200902016) and the Graduated Student Innovation Foundation of Shaanxi Normal University (No.2011CXS030).

Received Date: 2011-11-01
Rev Recd Date: 2012-04-01
Publish Date: 2013-01-05

Abstract

Abstract

Predicting function of unknown proteins in PPI (Protein-protein interaction) network is an important task of bioinformatics. The traditional clustering and functional flow algorithms performed not well in clustering PPI networks. Therefore this paper introduced the concepts of pheromone and state transition probability in the Ant colony optimization (ACO) algorithm to optimize the process of forming functional modules. The pheromone on the paths which the ants have passed by was updated via the accumulative strategy instead of constants in order to generate clusters as completely as possible. The experiments on MIPS dataset turned out that our approach was superior to the flow methods in terms of precision, recall and f-measure value, meantime reduced the time consumed.
- Ant colony optimization (ACO) algorithm,
- PPI networks,
- Pheromone

FullText(HTML)

References(21)

References

I. Xenarion, et al., “DIP, the database of interacting proteins:a research tool for studying cellular networks of protein interaction”,Nucleic Acids Research, Vol.30, No.1, pp.303-305, 2002.

S. Kerrien, Y. Alam-Faruque, B. Aranda, et al., “IntAct-opensource resource for molecular interaction data”, Nucleic AcidsResearch, Vol.32, No.Suppl.1, pp.D561-D565, 2007.

G.R. Mishra, M. Suresh, K. Kumaran, N. Kannabiran, etal., “Human protein reference database-2006 update”, NucleicAcids Research, Vol.34, No.Suppl.1, pp.D411-D414, 2006.

U. Guldener, M. Munsterkotter, M. Oesterheld, P. Pagel, et al.,“MPact: the MIPS protein interaction resource on yeast”, NucleicAcids Research, Vol.34, No.Suppl.1, pp.D436-D441, 2006.

D.J.Watts, S.H. Strogatz, “Collective dynamics of ‘small-world’networks”, Nature, Vol.393, pp.440-442, 1998.

S. Yook, Z. Oltvai, A. Barabasi, “Functional and topologicalcharacterization of protein interaction network”, Proteomics,Vol.4, No.4, pp.928-942, 2004.

A.L. Barabási, Z.N. Oltvai, “Network biology: understandingthe cell’s functional organization”, Nature Reviews: Genetics,Vol.5, No.2, pp.101-113, 2004.

Z.G. Zhou, X.F. Song, “Predicting protein-protein interactionsbased on ensemble classifiers”, Acta Electronica Sinica, Vol.38,No.6, pp.1464-1467, 2010. (in Chinese)

P.G. Sun, L. Gao, S.S. Han, “Identification of overlappingand non-overlapping community structure by fuzzy clusteringin complex networks”, Information Sciences, Vol.181, No.6,pp.1060-1071, 2011.

T. Berggard, S. Linse, P. James, “Methods for the detectionand analysis of protein-protein interactions”, Proteomics, Vol.7,No.16, pp.2833-2842, 2007.

N. Elena, J. Kam, A. Amit, et al., “Whole-proteome predictionof protein function via graph-theoretic analysis of interactionmaps”, Bioinformatics, Vol.21, No.1, pp.i302-i310, 2005.

C. Youngrae, H. Woochang, R. Murali, et al., “Semantic integrationto identify overlapping functional modules in proteininteraction networks”, BMC Bioinformatics, Vol.8, 2007.

A.D. Zhang, “Protein interaction networks”, Cambridge UniversityPress, New York, USA, 2009.

E. Bonabeau, M. Dorigo, G. Theraulaz, “Inspiration for optimizationfrom social insect behavior”, Nature, Vol.406, No.6,pp.39-42, 2000.

J.L. Deneubourg, et al., “The dynamics of collective sortingrobot-like ants and ant-like robot”, Proceedings of the FirstInternational Conference on Simulation of Adaptive Behavior:From Animals to Animals, pp.356-363, 1991.

E. Lumer, B. Faieta, “Diversity and adaptation in populationof clustering ants”, Proceedings of the Third International Conferenceon Simulation of Adaptive Behavior: From Animals toAnimals, pp.499-508, 1994.

Y. Yan, S.K. Mohamed, “An aggregated clustering approach usingmulti-ant colonies algorithms”, Pattern Recognition, Vol.39,No.7, pp.1278-1289, 2006.

N. Monmarché, M. Slimane, G. Venturini, “On improving clusteringin numerical databases with artificial ants”, Lecture Notesin Computer Science, Vol.1674, pp.626-635, 1999.

X.J. Lei, et al., “Joint strength based ant colony optimizationclustering algorithm for PPI networks”, Acta Electronica Sinica,Vol.40, No.4, pp.695-702, 2012. (in Chinese)

U. Güldener, M. Münsterkötter, G. Kastenmüller, N. Strack, etal., “CYGD: the comprehensive yeast genome database”, NucleicAcids Research, Vol.33, pp.D364-D368, 2005.

X.J. Lei, X. Huang, L. Shi, A.D. Zhang, “Clustering PPI databased on improved functional-flow model through quantumbehavedPSO”, Int. J. Data Mining and Bioinformatics, Vol.6,No.1, pp.42-60, 2012.

Relative Articles

Supplements(0)

Cited By

Proportional views