Special Issue – Nature Inspired Distributed ComputingNo Access

HYBRIDIZATION OF GENETIC AND QUANTUM ALGORITHM FOR GENE SELECTION AND CLASSIFICATION OF MICROARRAY DATA

ALLANI ABDERRAHIM

Institut Supérieur de Gestion, 41, Rue de la liberté, Cité Bouchoucha 2000, Bardo, Tunisie

Search for more papers by this author

EL-GHAZALI TALBI

LIFL-INRIA Futurs, Bât M3, Cité Scientifique, 59655 Villeneuve d'Ascq, France

King Saud University, Riyadh, Saudi Arabia

Search for more papers by this author

, and

MELLOULI KHALED

Institut des Hautes Etudes Commerciales de Carthage, Carthage Présidence Carthage, Tunisie

Search for more papers by this author

https://doi.org/10.1142/S0129054112400217Cited by:8 (Source: Crossref)

Abstract

In this work, we hybridize the Genetic Quantum Algorithm with the Support Vector Machines classifier for gene selection and classification of high dimensional Microarray Data. We named our algorithm GQA_SVM. Its purpose is to identify a small subset of genes that could be used to separate two classes of samples with high accuracy. A comparison of the approach with different methods of literature, in particular GA_SVM and PSO_SVM [2], was realized on six different datasets issued of microarray experiments dealing with cancer (leukemia, breast, colon, ovarian, prostate, and lung) and available on Web. The experiments clearified the very good performances of the method. The first contribution shows that the algorithm GQA_SVM is able to find genes of interest and improve the classification on a meaningful way. The second important contribution consists in the actual discovery of new and challenging results on datasets used.

Keywords:

References

K.-H. Han and J.-H. Kim, Genetic Quantum Algorithm and its Application to Combinatorial Optimization Problem, Proceedings of the 2000 Congress on Evolutionary Computation2 (IEEE Press, Piscataway, NJ, 2000) pp. 1354–1360. Google Scholar
E. Alba et al. , A Comparison of PSO and GA Approaches for Gene Selection and Classification of Microarray Data , Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2007) ( ACM Press , 2007 ) . Google Scholar
C. H. Bennettet al., Journal of Cryptography 5, 3 (1992). Google Scholar
C. H. Bennettet al., Physical Review Letters 70(13), 1895 (1993), DOI: 10.1103/PhysRevLett.70.1895. Crossref, Web of Science, Google Scholar
P. W. Shor, "Algorithms for Quantum Computation: Discrete Logarithms and Factoring", Proceedings, 35th Annual Symposium on Foundations of Computer Science, November 1994, pp. 124134 . Google Scholar
P. W. Shor, "Quantum Computing", Documenta Mathematica, vol. Extra Volume ICM, pp. 467-486, 1998 , http://east.camel.math.ca/EMIS/journals/DMJDMV/xvol-icm/00/Shor.MAN.html . Google Scholar
L. K. Grover, "A fast quantum mechanical algorithm for database search", Proceedings 28th Annual Symposium on the theory of Computing, May 1996, pp. 212-219 . Google Scholar
Amer Draa, Hichem Talbi, Mohamed Batouche, "A Quantum-Inspired Genetic Algorithm for Solving the N-Queens Problem", Vision & Computer Graphics Team, LIRE Laboratory, Computer Science Department, Engineering Faculty, Mentouri University, Constantine, Algeria, 7th ISPS'Algiers, May 2005 . Google Scholar
Amer Draa, Hichem Talbi, Mohamed Batouche, "A New Quantum-Inspired Genetic Algorithm for Solving the Travelling Salesman Problem", International Conference on Industrial Technology, IEEE Press, 2004 . Google Scholar
P. M. Narendra and K. Fukunaga, IEEE Trans. on computer, C 26(9), 917 (1977). Web of Science, Google Scholar
Koller D. and Sahami M., "Toward optimal feature selection". In: Proceedings of International Conference on Machine Learning, 1996 . Google Scholar
M. Dash and H. Liu, International Journal of Intelligent Data Analysis 1(3), 131 (1997). Crossref, Google Scholar
Statnikov A., Aliferis C. F., and Tsamardinos I. "Methods for Multicategory Cancer Diagnosis from Gene Expression Data: A Comprehensive Evaluation to Inform Decision Support System Development". Medinfo : 813-817, 2004 . Google Scholar
P. Pavlidis, I. Wapinski and W. S. Noble, Bioinformatics 20, 586 (2004), DOI: 10.1093/bioinformatics/btg461. Crossref, Web of Science, Google Scholar
T. Fureyet al., Bioinformatics 16(10), 906 (2000), DOI: 10.1093/bioinformatics/16.10.906. Crossref, Web of Science, Google Scholar
I. Guyonet al., Machine Learning 46(1-3), 389 (2002), DOI: 10.1023/A:1012487302797. Crossref, Web of Science, Google Scholar
E. B. Huerta, B. Duval and J.-K. Hao, A Hybrid GASVM Approach for Gene Selection and Classifcation of Microarray Data, Lecture Notes in Computer Science of EvoWorkshops3907, eds. F. Rothlaufet al. (Springer, 2006) pp. 34–44. Google Scholar
http://sdmc.lit.org.sg/GEDatasets/Datasets.html . Google Scholar
http://cs1.shu.edu.cn/gzli/data/mirror-kentridge.html . Google Scholar
http://cilab.ujn.edu.cn/dataset/leukemia%20cancer.rar http://cilab.ujn.edu.cn/dataset/lung_cancer.rar http://cilab.ujn.edu.cn/dataset/Colon%20data.rar http://cilab.ujn.edu.cn/dataset/Ovarian%20data.rar . Google Scholar
http://www.broad.mit.edu/cgi-bin/cancer/datasets.cgi . Google Scholar
S. Cahon, E.-G. Talbi and N. Melab, Paradiseo: A framework for parallel and distributed metaheuristics, Proc. of Internationa the Parallel and Distributed Processing Symposium (2003) pp. 144–155. Google Scholar
C.-C. Chang and C.-J. Lin. "LIBSVM: A library for support vector machines". Software available at URL 2002 , http://www.csie.ntu.edu.tw/~cjlin/libsvm . Google Scholar
Juliusdottiret al., Two-phase EA/K-NN for feature selection and classification in cancer microarray datasets, CIBCB (2005) pp. 1–8. Google Scholar
K. Deb and A. R. Reddy, "Classification of two-class cancer data reliably using evolutionary algorithms". Technical report, KanGAL Report No. 2003001, 2003 . Google Scholar
L. Yu and H. Liu, Redundancy based feature selection for microarry data, Proceedings of International Conference on Knowledge Discovery and Data Mining (Seattle, Washington, 2004) pp. 22–25. Google Scholar
B. Liuet al., BMC Bioinformatics 5, 136 (2004), DOI: 10.1186/1471-2105-5-136. Crossref, Web of Science, Google Scholar
M. Laiwan Chan, Informative Gene Discovery for Cancer Classification from Microarray Expression Data, Machine Learning for Signal Processing, 2005 IEEE Workshop on (2005) pp. 393–398. Google Scholar
Chen Liao and Shutao Li , Bioinformatics Research and Applications 4463 ( Springer , Berlin – Heidelberg , 2007 ) . Google Scholar
K.-H. Hanet al., Parallel Quantum-inspired Genetic Algorithm for Combinatorial Optimization Problem, Proceedings of the 2001 Congress on Evolutionary Computation2 (IEEE Press, Piscataway, NJ, 2001) pp. 1422–1429. Google Scholar
Amer Draa, Hichem Talbi and Mohamed Batouche, Une approche génétique quantique pour la fusion d'images multi-sources, CARI 2004 (2004) pp. 75–82. Google Scholar