An Advanced Nelder Mead Simplex Method for Clustering of Gene Expression Data

Authors: M. Pandi, K. Premalatha

Abstract:

The DNA microarray technology concurrently monitors the expression levels of thousands of genes during significant biological processes and across the related samples. The better understanding of functional genomics is obtained by extracting the patterns hidden in gene expression data. It is handled by clustering which reveals natural structures and identify interesting patterns in the underlying data. In the proposed work clustering gene expression data is done through an Advanced Nelder Mead (ANM) algorithm. Nelder Mead (NM) method is a method designed for optimization process. In Nelder Mead method, the vertices of a triangle are considered as the solutions. Many operations are performed on this triangle to obtain a better result. In the proposed work, the operations like reflection and expansion is eliminated and a new operation called spread-out is introduced. The spread-out operation will increase the global search area and thus provides a better result on optimization. The spread-out operation will give three points and the best among these three points will be used to replace the worst point. The experiment results are analyzed with optimization benchmark test functions and gene expression benchmark datasets. The results show that ANM outperforms NM in both benchmarks.

Keywords: Spread out, simplex, multi-minima, fitness function, optimization, search area, monocyte, solution, genomes.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1093600

References:

[1] Alon, U. Barkai, N. Notterman, D.A. Gish, K. Ybarra, S. Mack, D. and Levine, A.J. "Broad Patterns of Gene Expression Revealed by Clustering Analysis of Tumor and Normal Colon Tissues Probed by Oligonucleotide Array”, In Proc. of the Natl. Acad. Sci. U.S.A.,1999, Vol. 96, No. 12, pp. 6745-6750.
[2] C. Ding, "Analysis of Gene Expression Profiles: Class Discovery and Leaf Ordering”, In Proc. of the Int. Conf. Comput. Mol. Biol. (RECOMB), Berlin, Germany, 2002, pp. 27-136.
[3] Wei Liu, Bo Wang, Jarka Glassey, Elaine Martin, and Jian Zhao, "A novel methodology for finding the regulation on gene expression data”, Prog. Nat. Sci., Vol. 19, pp. 267-272, 2009.
[4] J.A. Nelder, and R. Mead, "A simplex method for function minimization”, Comput. J. Vol. 7, pp. 308–313, 1965.
[5] W. Spendley, G.R. Hext, and F.R. Himsworth, "Sequential Application of Simplex Designs in Optimisation and Evolutionary Operation”, Technometrics, Vol. 4, pp. 441–461, 1962.
[6] R. Krovi, "Genetic Algorithms for Clustering: A Preliminary Investigation”, In Proc. of the 25th Hawaii Int. Conf. Syst. Sci., 1992, Vol. 4, pp. 540-544.
[7] N. Durand, J.M. Alliot, W. Banzhaf, J. Daida, A.E. Eiben, M.H. Garzon, V. Honavar, M. Jakiela, R.E. Smith (Eds.), "A combined Nelder–Mead simplex and genetic algorithm”, In Proc. of the Genet. Evol. Comput. Conf. GECCO_99, Morgan Kaufmann, Orlando, FL, USA, 1999, pp. 1–7.
[8] L. Nazareth, P. Tseng, "Gilding the Lily: A Variant of the Nelder-Mead Algorithm Based on Golden-Section Search”, Comput. Optim. Appl, vol. 22, no. 1, pp. 133–144, 2002.
[9] A. Marco Luersen and Rodolphe Le Riche, "Globalised Nelder-Mead method for Engineering optimization”, J. Comput. Struct., Vol 3, 10 pages, 2004.
[10] F. Fazel, L. Ganming, L. Ziying, (2004) "Evaluation and optimization of clustering in gene expression data analysis”, BMC Bioinf. Vol. 20, No. 10, pp. 1535-1545, 2004.
[11] Vito Di Ges , Raffaele Giancarlo, Giosu Lo Bosco, Alessandra Raimondi and Davide Scaturro, "GenClust: A genetic algorithm for clustering gene expression data”, BMC Bioinf. Vol. 280, No.6, pp. 1-11, 2005.
[12] R. Chelouah and P. Siarry, "A hybrid method combining continuous Tabu search and NeldereMead simplex algorithms for the global optimization of multiminima functions”. Eur. J. Oper. Res. Vol. 161, No. 3, pp. 636-654, 2005.
[13] S.Y. Kim and H. Toshimitsu, "Evaluation of Clustering based on Preprocessing in Gene Expression Data”, World Acad. Sci. Eng. Technol., Int. J. Comput. Inf. Sci. Eng. Vol.1, No. 5, pp. 154-159, 2007.
[14] P.C.H. Ma, K.C.C. Chan, X. Yao, and D.K.Y. Chiu,"An evolutionary clustering algorithm for gene expression microarray data analysis”, IEEE Trans. Evol. Comput., Vol. 10, No. 3, pp. 296-314, 2006.
[15] R. Kustra, ”A factor analysis model for functional genomics”, BMC Bioinf., Vol. 216, No. 7, pp. 1-13, 2006.
[16] Dr. S C Satapathy et.al Article "An Efficient Algorithm for Data Clustering using improved Genetic Algorithm and Nelder Mead Simplex Search” IEEE Int. Conf. Comput. Intell. Multimedia Appl. Sivakasi, India Dec 2007.
[17] G. Kerr, H.J. Ruskin, M. Crane, and P. Doolan, "Techniques for clustering gene expression data”, Comput. Biol. Med., Vol. 38, pp. 283–293, 2007.
[18] Zhihua Du, YiweiWang, Zhen Ji, ”PK-means: A new algorithm for gene clustering”, Comput. Biol. Chem., Vol. 32, pp.243-247, 2008.
[19] Erwie Zahara, Yi-Tung Kao, "Hybrid Nelder-Mead simplex search and particle swarm optimization for constrained engineering design problems”, Expert. Syst. Appl. Vol. 36, No. 2, pp. 3880-3886, 2009.
[20] F. Gao, L. Han, "Implementing the Nelder-Mead Simplex Algorithm with Adaptive Parameters”, Comput. Optim. Appl, vol: 51. pp. 259-277, 2010.
[21] Rui Xu and D.C. Wunsch,” Clustering Algorithms in Biomedical Research: A Review”, IEEE Rev. Biomed. Eng., Vol. 3, pp. 120 – 154, 2010.
[22] Nam Pham and Bogdan M.Wilamowski, "Improved Nelder-Mead simplex method and applications”, J. Comput., Vol 3, issue 3, pp:55-63, 2011.
[23] L. Wang, Y. Xu, and L. Li, "Parameter identification of chaotic systems by hybrid Nelder – Mead simplex search and differential evolution algorithm”, Expert Syst. Appl., vol. 38, pp. 3238-3245, 2011.
[24] Sajid Nagi, D.K. Bhattacharyya, and J.K. Kalita, "Subspace Clustering in Gene Expression Data Analysis: A Survey, in Machine Intelligence: Recent Advances”, Narosa Publ., Delhi, pp. 211-219, 2011.
[25] J. Jacinth Salome and R.M. Suresh, "Efficient Clustering for Gene Expression Data”, Int. J. Comput. Appl., Vol. 47, pp. 30-35, 2012.
[26] An Liu, and Ming-Ta Yang, ”A New Hybrid Nelder-Mead Particle Swarm Optimization for Coordination Optimization of Directional Overcurrent Relays”, Math. Prob. Eng., Vol. 2012, pp. 1-18, 2012.
[27] P. A. Jaskowiak and R.J.G.B Campello, "Comparing correlation coefficients as dissimilarity measures for cancer classification in gene expression data”, Proc. Braz. Symp. Bioinf. Brasilia. Braz, 2011, pp. 1-8.
[28] R.Balamurugan A.M.Natarajan and K. Premalatha, "Comparative Study on Swarm Intelligence Techniques for Biclustering of Microarray Gene Expression Data.”, World Acad. Sci. Eng. Technol., Int. J. Comput. Inf. Sci. Eng. Vol.8, No. 2, pp. 4619-4625, 2014.
[29] P. Gray, W.E. Hart, L. Painton, C. Phillips, M. Trahan, and J. Wagner, ”A Survey of Global Optimization Methods”, Tech. Rep., Sandia Nat. Lab, 2000.
[30] P. Spellman, G. Sherlock, M.Q. Zhang, V.R. Iyer, K. Anders, M.B. Eisen, P.O. Brown, D. Botstein, and Futcher, (1998) "Comprehensive identification of cell cycle regulated genes of the yeast Saccharomyces Cerevisiae by microarray hybridization”, Mol. Biol. Cell, Vol. 9, pp - 3273-3297, 1998.
[31] R. J. Cho, M.J. Campbell, E.A. Winzeler, L. Steinmetz, A. Conway, L.W.Wolfsberg, A. Gabrielian, D. Landsman, D. Lockhart and R. Davis, (1998) ”A genome-wide transcriptional analysis of the mitotic cell cycle”, J. Mol. Cell..Vol:2, pp:65-73, 1998.
[32] X. Wen, S. Fuhrman, G.S. Michaels, G.S. Carr,D.B. Smith, J.L. Barker and R. Somogyi, ”Large scale temporal gene expression mapping of central nervous system development”. In Proc. of the Natl. Acad. Sci. U.S.A.2005, Vol:95.,pp:334-339.