Using Entropy as the Convergence Criteria of Ant Colony Optimization and the Application at Gene Chip Data Analysis

Chonghao      Gao; Xinping      Pang; Chongbao      Wang; Jingyue      Huang; Hui      Liu; Chengjiang      Zhu; Kunpei      Jin; Weiqi      Li; Pengtao      Zheng; Zihang      Zeng; Yanyu      Wei; Chaoyang      Pang

Abstract

Introduction: When Ant Colony Optimization algorithm (ACO) is adept at identifying the shortest path, the temporary solution is uncertain during the iterative process. All temporary solutions form a solution set.

Methods: Where each solution is random. That is, the solution set has entropy. When the solution tends to be stable, the entropy also converges to a fixed value. Therefore, it was proposed in this paper that apply entropy as a convergence criterion of ACO. The advantage of the proposed criterion is that it approximates the optimal convergence time of the algorithm.

Results: In order to prove the superiority of the entropy convergence criterion, it was used to cluster gene chip data, which were sampled from patients of Alzheimer’s Disease (AD). The clustering algorithm is compared with six typical clustering algorithms. The comparison shows that the ACO using entropy as a convergence criterion is of good quality.

Conclusion: At the same time, applying the presented algorithm, we analyzed the clustering characteristics of genes related to energy metabolism and found that as AD occurs, the entropy of the energy metabolism system decreases; that is, the system disorder decreases significantly.

Keywords: Ant colony algorithms, entropy, Alzheimer’s disease, gene chip data analysis, entropy convergence criterion, energy metabolism system.

[1]
Gambardella L, Dorigo M. Solving symmetric and asymmetric TSPs by ant colonies. Proceedings of the Proceedings of IEEE International Conference on Evolutionary Computation  1996; 622-7.
 [http://dx.doi.org/10.1109/ICEC.1996.542672]

[2]
Dorigo M, Gambardella LM. Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Trans Evol Comput  1997; 1(1): 53-66.
 [http://dx.doi.org/10.1109/4235.585892]

[3]
Dorigo M, Stützle T. The ant colony optimization metaheuristic: Algorithms, applications, and advances. In: Glover F, Kochenberger GA, Eds. Handbook of Metaheuristics.  Boston, MA: Springer US 2003; pp. 250-85.
 [http://dx.doi.org/10.1007/0-306-48056-5_9]

[4]
Dorigo M, Caro GD, Gambardella LM. Ant algorithms for discrete optimization. Artif Life  1999; 5(2): 137-72.
 [http://dx.doi.org/10.1162/106454699568728] [PMID: 10633574]

[5]
Shapiro J. Genetic algorithms in machine learning. Machine Learning and Its Applications.  Springer 1999; pp. 146-68.
 [http://dx.doi.org/10.1007/3-540-44673-7_7.]

[6]
Ball M, Magnanti T, Monma C, Nemhauser G. Handbooks in operation research and management science.  Elsevier Science 1995; 8.

[7]
Kirkpatrick S, Gelatt CD Jr, Vecchi MP. Optimization by simulated annealing. Science  1983; 220(4598): 671-80.
 [http://dx.doi.org/10.1126/science.220.4598.671] [PMID: 17813860]

[8]
Glover F, Mulvey JM, Hoyland K. Solving dynamic stochastic control problems in finance using tabu search with variable scaling. In: Osman IH, Kelly JP, Eds. Meta-Heuristics: Theory and Applications.  Boston, MA: Springer US 1996; pp. 429-48.
 [http://dx.doi.org/10.1007/978-1-4613-1361-8_26]

[9]
Goldberg DE, Holland JH. Genetic algorithms and machine learning. Machine Learning  1989; 95-9.
 [http://dx.doi.org/10.1023/A:1022602019183.]

[10]
Gambardella LM, Dorigo M. Ant-Q: A reinforcement learning approach to the traveling salesman problem. Machine learning proceedings 1995  1995; 252-60.
 [http://dx.doi.org/10.1016/B978-1-55860-377-6.50039-6]

[11]
Gambardella LM, Taillard ÉD, Dorigo M. Ant colonies for the quadratic assignment problem. J Oper Res Soc  1999; 50(2): 167-76.
 [http://dx.doi.org/10.1057/palgrave.jors.2600676]

[12]
Bullnheimer B, Hartl RF, Strauss C. Applying the ANT system to the vehicle routing problem.  2nd International Conference on Metaheuristics - MIC97. Sophia-Antipolis, France. 1997.
 [http://dx.doi.org/10.1007/978-1-4615-5775-3_20]

[13]
Parpinelli RS, Lopes HS, Freitas AA. Data mining with an ant colony optimization algorithm. IEEE Trans Evol Comput  2002; 6(4): 321-32.
 [http://dx.doi.org/10.1109/TEVC.2002.802452]

[14]
Gutjahr WJ. ACO algorithms with guaranteed convergence to the optimal solution. Inf Process Lett  2002; 82(3): 145-53.
 [http://dx.doi.org/10.1016/S0020-0190(01)00258-7]

[15]
Duan H. Ant colony optimization: Principle, convergence and application. Handbook of Swarm Intelligence: Concepts, Principles and Applications.  Springer 2011; pp. 373-88.
 [http://dx.doi.org/10.1007/978-3-642-17390-5_16]

[16]
Yoo JH, La RJ, Makowski AM. Convergence results for ant routing. Proceedings of the proceedings of the conference on information sciences and systems 2004.

[17]
Yoo JH, La RJ, Makowski AM. Convergence of ant routing algorithms–Results for a simple parallel network and perspectives. Technical Report CSHCN 2003-44, University of Maryland 2003.

[18]
Sun T, Wang XK, Liu YX, Zhang Mj. Ant algorithm and analysis on its convergence. Minimicro Systems-Shenyang  2003; 24: 1524-7.

[19]
Ding JL, Chen ZQ, Yuan ZZ. On the Markov convergence analysis for the combination of genetic algorithm and ant algorithm. Acta Automatica Sinica  2004; 30: 629-34.

[20]
Hou YH, Wu YW, Lu LJ, Xiong XY. Generalized ant colony optimization for economic dispatch of power systems. Proceedings international conference on power system technology.  Kunming, China. 2002; pp. 225-9.
 [http://dx.doi.org/10.1109/ICPST.2002.1053539]

[21]
Shannon CE. A mathematical theory of communication. Bell Syst Tech J  1948; 27(3): 379-423.
 [http://dx.doi.org/10.1002/j.1538-7305.1948.tb01338.x]

[22]
Guo W, Sun Y, Pang X, et al. A novel crossover operator based on grey wolf optimizer applied to feature selection problem. Genetic and Evolutionary Computing.   2024; pp. 98-107.
 [http://dx.doi.org/10.1007/978-981-99-9412-0_11.]

[23]
Sun X, Shu W, Zhang Y, et al. Identification of Alzheimer’s disease associated genes through explicable deep learning and bioinformatic. Proceedings of the 2023 IEEE 4th international conference on pattern recognition and machine learning (PRML)  2003; 320-7.
 [http://dx.doi.org/10.1109/PRML59573.2023.10348276]

[24]
Chelly D Z, Avdeyev P, Bayzid MS. Biological computation and computational biology: survey, challenges, and discussion. Artif Intell Rev  2021; 54(6): 4169-235.
 [http://dx.doi.org/10.1007/s10462-020-09951-1]

[25]
Zhang Y, Kiryu H. Identification of oxidative stress-related genes differentially expressed in Alzheimer’s disease and construction of a hub gene-based diagnostic model. Sci Rep  2023; 13(1): 6817.
 [http://dx.doi.org/10.1038/s41598-023-34021-1] [PMID: 37100862]

[26]
Stützle T, Dorigo M. A short convergence proof for a class of ant colony optimization algorithms. IEEE Trans Evol Comput  2002; 6(4): 358-65.
 [http://dx.doi.org/10.1109/TEVC.2002.802444]

[27]
Colorni A, Dorigo M, Maniezzo V, et al. Distributed optimization by ant colonies. Proceedings of the Proceedings of the first European conference on artificial life.  Paris, France. 1991; pp. 142: 134-42.

[28]
Pang CY. Vector quantization and image compression. Ph D thesis, Department of Computer Science 2002.

[29]
Liu T, Porter J, Zhao C, et al. TADKB: Family classification and a knowledge base of topologically associating domains. BMC Genomics  2019; 20(1): 217.
 [http://dx.doi.org/10.1186/s12864-019-5551-2] [PMID: 30871473]

[30]
Ferrer-Font L, Mayer JU, Old S, Hermans IF, Irish J, Price KM. High-dimensional data analysis algorithms yield comparable results for mass cytometry and spectral flow cytometry data. Cytometry A  2020; 97(8): 824-31.
 [http://dx.doi.org/10.1002/cyto.a.24016] [PMID: 32293794]

[31]
Hartigan JA. Clustering algorithms. John Wiley & Sons, Inc. 1975.

[32]
Eisen MB, Spellman PT, Brown PO, Botstein D. Cluster analysis and display of genome-wide expression patterns. Proc Natl Acad Sci USA  1998; 95(25): 14863-8.
 [http://dx.doi.org/10.1073/pnas.95.25.14863] [PMID: 9843981]

[33]
Saldanha AJ. Java Treeview—extensible visualization of microarray data. Bioinformatics  2004; 20(17): 3246-8.
 [http://dx.doi.org/10.1093/bioinformatics/bth349] [PMID: 15180930]

[34]
Kaufman L, Rousseeuw PJ. Finding groups in data: An introduction to cluster analysis. John Wiley 1990.
 [http://dx.doi.org/10.2307/2532178.]

[35]
Pirim H, Ekşioğlu B, Perkins AD, Yüceer Ç. Clustering of high throughput gene expression data. Comput Oper Res  2012; 39(12): 3046-61.
 [http://dx.doi.org/10.1016/j.cor.2012.03.008] [PMID: 23144527]

[36]
Cheng H, Yang S, Cao J. Dynamic genetic algorithms for the dynamic load balanced clustering problem in mobile ad hoc networks. Expert Syst Appl  2013; 40(4): 1381-92.
 [http://dx.doi.org/10.1016/j.eswa.2012.08.050]

[37]
Dhillon IS. Co-clustering documents and words using bipartite spectral graph partitioning. 2001.
 [http://dx.doi.org/10.1145/502512.502550]

[38]
Ciaramella A, Nardone D, Staiano A. Data integration by fuzzy similarity-based hierarchical clustering. BMC Bioinformatics  2020; 21(S10): 350.
 [http://dx.doi.org/10.1186/s12859-020-03567-6] [PMID: 32838739]

[39]
Chatterjee S, Das A. An ensemble algorithm integrating consensus-clustering with feature weighting based ranking and probabilistic fuzzy logic-multilayer perceptron classifier for diagnosis and staging of breast cancer using heterogeneous datasets. Appl Intell  2023; 53(11): 13882-923.
 [http://dx.doi.org/10.1007/s10489-022-04157-0]

[40]
Chang H, Yeung DY. Robust path-based spectral clustering. Pattern Recognit  2008; 41(1): 191-203.
 [http://dx.doi.org/10.1016/j.patcog.2007.04.010]

[41]
Li Z, Nie F, Chang X, Yang Y, Zhang C, Sebe N. Dynamic affinity graph construction for spectral clustering using multiple features. IEEE Trans Neural Netw Learn Syst  2018; 29(12): 6323-32.
 [http://dx.doi.org/10.1109/TNNLS.2018.2829867] [PMID: 29994548]

[42]
Lv Y, Zhu X, Zhu Z, Qu A. Nonparametric cluster analysis on multiple outcomes of longitudinal data. Stat Sin  2020; 30: 1829-56.
 [http://dx.doi.org/10.5705/ss.202018.0032]

[43]
Ren Y, Wang N, Li M, Xu Z. Deep density-based image clustering. Knowl Base Syst  2020; 197: 105841.
 [http://dx.doi.org/10.1016/j.knosys.2020.105841]

[44]
Woodman RJ, Mangoni AA. A comprehensive review of machine learning algorithms and their application in geriatric medicine: Present and future. Aging Clin Exp Res  2023; 35(11): 2363-97.
 [http://dx.doi.org/10.1007/s40520-023-02552-2] [PMID: 37682491]

[45]
Guo YB, Zheng ZX, Kong LJ, et al. A novel multi-view bi-clustering method for identifying abnormal co-occurrence medical visit behaviors. Methods  2022; 207: 65-73.
 [http://dx.doi.org/10.1016/j.ymeth.2022.09.004] [PMID: 36122881]

[46]
Li H, Herfort B, Huang W, Zia M, Zipf A. Exploration of OpenStreetMap missing built-up areas using twitter hierarchical clustering and deep learning in Mozambique. ISPRS J Photogramm Remote Sens  2020; 166: 41-51.
 [http://dx.doi.org/10.1016/j.isprsjprs.2020.05.007]

[47]
Wu X, Shi Z, Zou Z. A geographic information-driven method and a new large scale dataset for remote sensing cloud/snow detection. ISPRS J Photogramm Remote Sens  2021; 174: 87-104.
 [http://dx.doi.org/10.1016/j.isprsjprs.2021.01.023]

[48]
Miller BF, Bambah-Mukku D, Dulac C, Zhuang X, Fan J. Characterizing spatial gene expression heterogeneity in spatially resolved single-cell transcriptomic data with nonuniform cellular densities. Genome Res  2021; 31(10): 1843-55.
 [http://dx.doi.org/10.1101/gr.271288.120] [PMID: 34035045]

[49]
Sheng W, Tucker A, Liu X. A niching genetic k-means algorithm and its applications to gene expression data. Soft Comput  2010; 14(1): 9-19.
 [http://dx.doi.org/10.1007/s00500-008-0386-9]

[50]
Abdel-Maksoud E, Elmogy M, Al-Awadi R. Brain tumor segmentation based on a hybrid clustering technique. Egyptian Inform J  2015; 16(1): 71-81.
 [http://dx.doi.org/10.1016/j.eij.2015.01.003]

[51]
Karim MR, Beyan O, Zappa A, et al. Deep learning-based clustering approaches for bioinformatics. Brief Bioinform  2021; 22(1): 393-415.
 [http://dx.doi.org/10.1093/bib/bbz170] [PMID: 32008043]

[52]
Tang T, Chen S, Zhao M, Huang W, Luo J. Very large-scale data classification based on K-means clustering and multi-kernel SVM. Soft Comput  2019; 23(11): 3793-801.
 [http://dx.doi.org/10.1007/s00500-018-3041-0]

[53]
Yan D, Huang L, Jordan MI. Fast approximate spectral clustering. Proceedings of the proceedings of the 15th ACM SIGKDD international conference on knowledge discovery and data mining. Paris, France. 2009.
 [http://dx.doi.org/10.1145/1557019.1557118.]

[54]
Zhang GY, Zhou YR, Wang CD, Huang D, He XY. Joint representation learning for multi-view subspace clustering. Expert Syst Appl  2021; 166: 113913.
 [http://dx.doi.org/10.1016/j.eswa.2020.113913]

[55]
Zhang Q, Chen B, Yang P, Wu J, Pang X, Pang C. Bioinformatics-based study reveals that AP2M1 is regulated by the circRNA-miRNA-mRNA interaction network and affects Alzheimer’s disease. Front Genet  2022; 13: 1049786.
 [http://dx.doi.org/10.3389/fgene.2022.1049786] [PMID: 36468008]

[56]
Zhang Q, Yang P, Pang X, et al. Preliminary exploration of the co-regulation of Alzheimer’s disease pathogenic genes by microRNAs and transcription factors. Front Aging Neurosci  2022; 14: 1069606.
 [http://dx.doi.org/10.3389/fnagi.2022.1069606] [PMID: 36561136]

[57]
Xiong J, Pang X, Song X, Yang L, Pang C. The coherence between PSMC6 and α-ring in the 26S proteasome is associated with Alzheimer’s disease. Front Mol Neurosci  2024; 16: 1330853.
 [http://dx.doi.org/10.3389/fnmol.2023.1330853] [PMID: 38357597]

[58]
Yang L, Pang X, Guo W, et al. An exploration of the coherent effects between METTL3 and NDUFA10 on Alzheimer’s disease. Int J Mol Sci  2023; 24(12): 10111.
 [http://dx.doi.org/10.3390/ijms241210111] [PMID: 37373264]

[59]
Yang X, Guo W, Yang L, et al. The relationship between protein modified folding molecular network and Alzheimer’s disease pathogenesis based on BAG2-HSC70-STUB1-MAPT expression patterns analysis. Front Aging Neurosci  2023; 15: 1090400.
 [http://dx.doi.org/10.3389/fnagi.2023.1090400] [PMID: 37251806]

[60]
Liu Z, Chaillou T, Santos Alves E, et al. Mitochondrial NDUFA4L2 is a novel regulator of skeletal muscle mass and force. FASEB J  2021; 35(12): e22010.
 [http://dx.doi.org/10.1096/fj.202100066R] [PMID: 34724256]

[61]
Hou T, Zhang R, Jian C, et al. NDUFAB1 confers cardio-protection by enhancing mitochondrial bioenergetics through coordination of respiratory complex and supercomplex assembly. Cell Res  2019; 29(9): 754-66.
 [http://dx.doi.org/10.1038/s41422-019-0208-x] [PMID: 31366990]

[62]
Huttula S, Väyrynen H, Helisalmi S, et al. NDUFA1 p.Gly32Arg variant in early-onset dementia. Neurobiol Aging  2022; 114: 113-6.
 [http://dx.doi.org/10.1016/j.neurobiolaging.2021.09.026] [PMID: 35131137]

[63]
Potluri P, Davila A, Ruiz-Pesini E, et al. A novel NDUFA1 mutation leads to a progressive mitochondrial complex I-specific neurodegenerative disease. Mol Genet Metab  2009; 96(4): 189-95.
 [http://dx.doi.org/10.1016/j.ymgme.2008.12.004] [PMID: 19185523]

[64]
Pan JS, Zhang LG, Wang RB, Snášel V, Chu SC. Gannet optimization algorithm: A 775 new metaheuristic algorithm for solving engineering optimization problems. Mathematics and 776. Jisuanji Fangzhen  2022; 202: 343-73.

[65]
Song PC, Chu SC, Pan JS, Yang H. Simplified Phasmatodea population evolution algorithm for optimization. Complex & Intelligent Systems  2022; 8(4): 2749-67.
 [http://dx.doi.org/10.1007/s40747-021-00402-0]

[66]
Yu L, Tan X, Luo D, et al. Chebyshev inequality and the identification of genes associated with Alzheimer’s disease. Genetic and Evolutionary Computing.  Springer 2024; pp. 87-97.
 [http://dx.doi.org/10.1007/978-981-99-9412-0_10.]

Cite As

Current Alzheimer Research

Using Entropy as the Convergence Criteria of Ant Colony Optimization and the Application at Gene Chip Data Analysis

Abstract