Comparative Study on Swarm Intelligence Techniques for Biclustering of Microarray Gene Expression Data

Authors: R. Balamurugan, A. M. Natarajan, K. Premalatha

Abstract:

Microarray gene expression data play a vital in biological processes, gene regulation and disease mechanism. Biclustering in gene expression data is a subset of the genes indicating consistent patterns under the subset of the conditions. Finding a biclustering is an optimization problem. In recent years, swarm intelligence techniques are popular due to the fact that many real-world problems are increasingly large, complex and dynamic. By reasons of the size and complexity of the problems, it is necessary to find an optimization technique whose efficiency is measured by finding the near optimal solution within a reasonable amount of time. In this paper, the algorithmic concepts of the Particle Swarm Optimization (PSO), Shuffled Frog Leaping (SFL) and Cuckoo Search (CS) algorithms have been analyzed for the four benchmark gene expression dataset. The experiment results show that CS outperforms PSO and SFL for 3 datasets and SFL give better performance in one dataset. Also this work determines the biological relevance of the biclusters with Gene Ontology in terms of function, process and component.

Keywords: Particle swarm optimization, Shuffled frog leaping, Cuckoo search, biclustering, gene expression data.

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

References:

[1] D.J. Lockhart, and E.A. Winzeler, "Genomics, gene expression and DNA arrays,” Nature, vol. 405, pp. 827-836, June 2000.
[2] C.L. Liu, Introduction to Combinatorial Mathematics. New York, McGraw-Hill Publication, 1968.
[3] F. Divina, and J.S. Aguilar-Ruiz, "Biclustering of expression data with evolutionary computation,” IEEE Trans. Knowl. Data Eng., vol. 18, no. 5, pp. 590-602, May 2006.
[4] A. Tanay, R. Sharan, and R. Shamir, "Discovering statistically significant biclusters in gene expression data,” BMC bioinf., vol. 18, pp. 136-144, March 2002.
[5] S.C. Madeira, and A.L. Oliveira, "Biclustering algorithms for biological data analysis: A survey,” IEEE/ACM Trans. Comput. Biol. Bioinf., vol. 1, no. 1, pp. 24-45, Jan. 2004.
[6] Y. Cheng, and G.M. Church, "Biclustering of Expression Data,” in Proc. of the 8th Conf. Intel. Sys. Mol. Biol., Menlo Park, United States, 2000, pp. 93-103.
[7] T. Murali, and S. Kasif, "Extracting conserved gene expression motifs from gene expression data,” in Pacific Symposium on Bio computing, Boston University, United States, 2003, pp. 77-88.
[8] A. Ben-Dor, B. Chor, R. Karp, and Z. Yakhini, "Discovering local structure in gene expression data: The order-preserving submatrix problem,” J. Comput. Biol., vol. 10, no. 4, pp. 373-384, 2003.
[9] S. Bergmann, J. Ihmels, and N. Barkai. "Iterative signature algorithm for the analysis of large-scale gene expression data,” Phys. Rev. E, vol. 67, pp. 1-18, March 2003.
[10] S. Mitra, and H. Banka. "Multi-objective evolutionary biclustering of gene expression data,” Pattern Recognit. Lett., vol. 39, no. 12, pp. 2464-2477, Dec. 2006.
[11] X. Liu, and L. Wang, "Computing the maximum similarity bi-clusters of gene expression data,” BMC bioinf., vol. 23, no. 1, pp. 50-56, Oct. 2007.
[12] P. DiMaggio, S. McAllister, C. Floudas, X. Feng, J. Rabinowitz, and H. Rabitz, "Biclustering via optimal re-ordering of data matrices in systems biology: rigorous methods and comparative studies,” BMC bioinf., vol. 9, no. 1, pp. 458-467, Oct. 2008.
[13] J. Liu, Z. Li, X. Hu, and Y. Chen, "Biclustering of microarray data with mospo based on crowding distance,” BMC bioinf., vol. 10, no. 9, April 2009.
[14] G.P. Coelho, F.O. de Franca, and F.J.V. Zuben, "Multi-objective biclustering: When non-dominated solutions are not enough,” J. Math. Model. Algorithms, vol. 8, no. 2, pp. 175-202, June 2009.
[15] W. Ayadi, M. Elloumi, and J. Hao, "Pattern-driven neighborhood search for biclustering microarray data,” BMC bioinf., vol. 13, no. 7, May, 2012.
[16] Q. Huang, D. Tao, X. Li, and A.W.C. Liew, "Parallelized evolutionary learning for detection of biclusters in gene expression data,” IEEE/ACM Trans.Comput. Biol. and Bioinf., vol. 9, no. 1, pp. 560-570, April 2012.
[17] A. Painsky, and S. Rosset, "Exclusive Row Biclustering for Gene Expression Using a Combinatorial Auction Approach,” in Proc. IEEE 12th Inter. Conf. Data Mining, Belgium, pp.1056-1061, Dec. 2012.
[18] S. Roy, D.K. Bhattacharyya, and J.K. Kalita, "CoBi: Pattern Based Co-Regulated Biclustering of Gene Expression Data,” Pattern Recognit. Lett., vol. 34, no. 14, pp. 1669-1678, Oct. 2013.
[19] B. Boutsinas, "A New Biclustering Algorithm Based On Association Rule Mining,” Int. J. Artif. Intell. Tools, vol. 30, no. 3, 2013
[20] A. Schrijver, Theory of Linear and Integer Programming, New York, John Wiley & Sons, 1998.
[21] J. Nocedal, and S. J. Wright, Numerical Optimization, Springer Series in Operations Research. Springer, 1999.
[22] D.P. Bertsekas, Dynamic Programming and Optimal Control. 2nd ed. Athena Scientific, Belmont, Massachusetts, USA, 2000.
[23] J.A. Nelder, and R. Mead, "A simplex method for function minimization,” Comput. J., vol. 7, no. 2, pp. 308-313, 1965.
[24] M. Avriel, Nonlinear Programming: Analysis and Methods, United Kingdom, Dover Publishing, 2003.
[25] J. Kennedy, and R.C. Eberhart, Particle swarm optimization. in Proc. IEEE Inter. Conf. Neural Networks, Piscataway, NJ, United states, pp. 1942-1948, 1995.
[26] C.W. Reynolds, "Flocks, herbs, and schools: A distributed behavioral model,” in Proc. 14th annu. conf. Comput. graphics and interactive techniques, New York, vol. 21, July 1987, pp. 25-34.
[27] E.O. Wilson, Sociobiology: The new synthesis, Massachusetts, Belknap Press, Cambridge, 1975.
[28] M.M. Eusuff, K. Lansey, and F.Pasha, "Shuffled frog-leaping algorithm: a memetic meta-heuristic for discrete optimization,” Eng. Optim., vol. 38, no. 2, pp. 129-154, Jan. 2006.
[29] M.M. Eusuf, K.E. Lansey, "Optimization of water distribution network design using the shuffled frog leaping algorithm,” J. Water Resour. Plann. Manage, vol. 129, no. 3, pp. 210-225, May 2003.
[30] Q.Y. Duan, V. K. Gupta, and S. Sorooshian, "Shuffled complex evolution approach for effective and efficient global minimization,” J. Optim. Theory Appl., vol. 76, pp. 502-521, March 1993.
[31] X.S. Yang, and S. Deb, "Engineering optimisation by Cuckoo search” Int. J. Math. Modeil. Numer. optim., vol. 1, no. 4, pp. 330-343, Dec. 2010.
[32] A.P. Gasch, P.T. Spellman, C.M. Kao, O. Carmel Harel, M.B. Eisen, G. Storz, D. Botstein, and P.O. Brown, "Genomic Expression Programs in the Response of Yeast Cells to Environmental Changes,” Mol. Biol. Cell., vol. 11, no. 12, pp. 4241-4257, Oct. 2000.
[33] S. Bleuler, A. Prelic, and E. Zitzler, "An EA framework for biclustering of gene expression data,” in Congress of IEEE on Evolutionary Comput., Switzerland, vol. 1, 2004, pp. 166-173.
[34] R. Cho, M.J. Campbell, A.E. Winzeler, L. Steinmetz, and A. Conway, "Genome-Wide Transcriptional Analysis of the Mitotic Cell Cycle,” Mol. Cell, vol. 2, no. 1, pp. 65-73, July 1998.
[35] X. Wen, S. Fuhrman, G.S. Michaels, D.B. Carr, S. Smith, J.L. Barker, and R. Somogyi, "Large-scale temporal gene expression mapping of central nervous system development,” in Proc. National Academy of sciences, vol. 95, no.1, pp. 334-339, Nov. 1998.
[36] Saccharomyces Genome Database Source: http://www.yeastgenome.org/cgibin/GO/goTermFinder.pl.