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.

Clustering PPI Data Based on Ant Colony Optimization Algorithm

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
  • 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.
  • loading
  • 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.
  • 加载中


    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (386) PDF downloads(1344) Cited by()
    Proportional views


    DownLoad:  Full-Size Img  PowerPoint