In order to efficiently explore and exploit large search space, quantum variant of genetic algorithm has been suggested in literature. It utilizes quantum computing principle and genetic operators. Despite the use of the quantum variant of GA, memory and computation time requirements for high dimensional data like microarrays are huge. In this paper, we propose a hybrid approach, ClusterQGA, that uses clustering to select a small set of non-redundant representative genes and then applies Quantum Genetic Algorithm to determine a minimal set of relevant and non-redundant genes. Also a new fitness function is proposed to reduce number of genes without sacrificing the classification accuracy. The effectiveness of the proposed approach in comparison to existing methods in terms of classification accuracy and number of features has been experimentally established for both binary and multi-class publicly available cancer microarray datasets. The proposed approach reduces the computation time of Quantum Genetic Algorithm for high dimension microarray data.
AbderrahimA., TalbiG. and KhaledM., Hybridization of genetic and quantum algorithm for gene selection and classification of microarray data, Journal of Foundations of Computer Science23(2) (2012).
2.
AgrawalR.K. and BalaR., A hybrid approach for selection of relevant features for microarray datasets, International Journal of Computer and Information Engineering1(2) (2007).
3.
AlbaE., Garca-NietoJ., JourdanL. and TalbiE.G., A comparison of PSO and GA approaches for gene selection and classification of microarray data, in: Genetic and Evolutionary Computation Conference, ACM Press, (2007).
4.
AlonU., BarkaiN., NottermanD.A., GishK., YbarraS., MackD. and LevineA.J., Broad patterns of gene expression revealed by clustering analysis of tumor and normal colon tissues probed by oligo-nucleotide array, Proc Nat'l Academy of Science9612 (1999), 6745-6750.
5.
Alonso-GonzalezC.J., Moro-SanchoQ.I. and Simon-HurtadoA., Varela-arrabal, microarray gene expression classification with few genes: Criteria to combine attribute selection and classification methods, Expert Systems with Applications39 (2012), 7270-7280.
6.
AlshamlanH.M., BadrG.H. and AlohaliY.A., The performance of bio-inspired evolutionary gene selection methods for cancer classification using microarray dataset, International Journal of Bioscience, Biochemistry and Bioinformatics4(3) (2014), 166-170.
7.
AlshamlanH., BadrG. and Alohali1Y., mRMR-ABC: A hybrid gene selection algorithm for cancer classification using microarray gene expression profiling, BioMed Research International, ID 604910, (2015).
8.
BittnerM., MeltzerP., ChenY., JiangY., SeftorE. and HendrixM., Molecular classification of cutaneous malignant melanoma by gene expression profiling, Nature406 (2000), 536-540.
9.
Bolón-CanedoV., Sánchez-MaroñoN., Alonso-BetanzosA., BenítezJ.M. and HerreraF., A review of microarray datasets and applied feature selection methods, Information Sciences282 (2014), 111-135.
10.
ChangC.C. and LinC.J., LIBSVM: A library for support vector machines, 2002. http://www.csie.ntu.edu.tw/cjlin/libsvm.
11.
ChopraP., LeeJ., KangJ. and LeeS., Improving cancer classification accuracy using gene pairs, PLoS ONE5(12) (2010).
12.
CoverT. and HartP., Nearest neighbor pattern classification, IEEE Transactions on Information Theory13 (1967), 21-27.
13.
CrossmanL., MoriM., HsiehY., LangeT., PaschkaP. and HarringtonC., Chronic myeloid leukemia white cells from cytogenetic responders and non responders to imatinib have very similar gene expression signatures, in: Haematologica90 (2005), 459-464.
14.
DraaA., TalbiH. and BatoucheM., A new quantum-inspired genetic algorithm for solving the travelling salesman problem, International Conference on Industrial Technology, IEEE Press, (2004).
15.
FisherR., The use of multiple measurements in taxonomic problems, Annals of Eugenics7 (1936), 179-188.
16.
FureyT., CristianiniN., DuffyN., BednarskiD.W., SchummerM. and HausslerD., Support vector machines classification and validation of cancer tissue samples using microarray expression data, Bioinformatics16(10) (2000), 906-914.
17.
GheyasI.A. and SmithL.S., Feature subset selection in large dimensionality domains, Pattern Recognition43 (2010), 5-13.
18.
GohL. and KasabovN., An integrated feature selection and classification to select minimum number of variables on the case study of gene expression data, Journal of Bioinformatics and Computational Biology35 (2005), 1107-1136.
19.
GoldbergD.E., Genetic algorithm in search optimization and machine learning, Addison Wesley, 1989.
20.
GolubT., SlonimD., TamayoP., HuardC., GaasenbeekM., MesirovJ. et al., Molecular classification of cancer: Class discovery and class prediction by gene expression monitoring, Science286 (1999), 531-537.
21.
GuyonI. and ElisseffA., An introduction to variable and feature selection, Journal of Machine Learning Research3 (2003), 1157-1182.
22.
GuyonJ., WestonS. and BarnhillV.V., Gene selection for cancer classification using support vector machines, Machine Learning46(1-3) (2002), 389-422.
23.
HanK.H. and KimJ.H., Genetic quantum algorithm and its application to combinatorial optimization problem, in: Congress on Evolutionary Computation, Piscataway, NJ: IEEE Press2 (2000), 1354-1360.
24.
HongJ.H. and ChoS.B., Efficient huge-scale feature selection with speciated genetic algorithm, Pattern Recognition Letters27(2) (2006), 143-150.
25.
HongJ.H. and ChoS.B., The classification of cancer based on DNA microarray data that uses diverse ensemble genetic programming, Artif Intell Med36 (2006), 43-58.
26.
KhanJ., WeiJ., RingerM., SaalL., LadanyiM., WestermannF. et al., Classification and diagnostic prediction of cancers using gene expression profiling and artificial neural networks, Nature Medicine76 (2001), 673-679.
27.
KiraK. and RendellL.A., The feature selection problem: Traditional methods and a new algorithm, in: AAAI-92 Proceedings (1992), 129-134.
28.
KohaviR. and JohnG., Wrapper for feature subset selection, Artificial Intelligence97(1-2) (1997), 273-324.
29.
KollerD. and SahamiM., Towards optimal feature selection, in: proceedings of 13th International Conference on Machine LearningItaly, Morgan Kaufmann, CA, (1996).
30.
KononenkoI., Estimating attributes: Analysis and extensions of RELIEF, in: European Conference on Machine Learning, (1994).
31.
LaiC., ReindersM., Van'tV.L. and WesselsL., A comparison of univariate and multivariate gene selection techniques for classification of cancer datasets, BMC Bioinformatics7 (2006), 235.
32.
LazarC., TaminauJ. and MeganchS., A survey on filter techniques for feature selection in gene expression microarray analysis, IEEE/ACM Trans on Comp Bio and Bioinformatics9(4) (2012).
33.
LiL., WeinbergC., DardenT. and PedersenL., Gene selection for sample classification based on gene expression data: Study of sensitivity to choice of parameters of the GA/KNN method, Bioinformatics17 (2001), 1131-1142.
34.
LiX., PengS., ZhanX., ZhangJ. and XuY., Comparison of feature selection methods for multiclass cancer classification based on microarray data, 4th International Conference on Biomedical Engineering and Informatics (BMEI)3 (2011), 1692-1696.
35.
LiuZ., PhanS., FamiliF., PanY. et al., A multi-strategy approach to informative gene identification from gene expression data, J Bioinform Comput Biol8 (2010), 19-38.
36.
MooreM.P. and NarayananA., Quantum inspired computing, Technical Report, 1995, http://www.dcs.exeter.ac.uk.
37.
MukherjeeS., Classifying microarray data using support vector machines, Boston, MA, ch. 9, 2003, 166-185.
38.
NuttC.L., ManiD.R., BetenskyR.A., TamayoP., CairncrossJ.G., LaddC., PohlU., HartmannC., McLaughlinM.E., BatchelorT.T., BlackP.M., Von DeimlingA., PomeroyS.L., GolubT.R. and LouisD.N., Gene expression based classification of malignant gliomas correlates better with survival than histological classification, Cancer Res63(7) (2003), 1602-1607.
39.
PattersonG. and ZhangM., Fitness functions in genetic programming for classification with unbalanced data, LNAI4830 (2007), 769-775.
40.
PengH., LongF. and DingC., Feature selection based on mutual information: Criteria of max-dependency, max-relevance, and min-redundancy, IEEE Transactions on Pattern Analysis and Machine Intelligence27(8) (2005), 1226-1238.
41.
PengS. and XuQ., Molecular classification of cancer types from microarray data using combination of genetic algorithm and support vector machine, Science Direct FEBS Letters555(2) (2010), 358-362.
42.
PiroozniaM., YangJ.Y., YangM.Q. and DengY., A comparative study of different machine learning methods on microarray gene expression data, BMC Genomics9(1) (2008), S13.
43.
PomeroyS.L., TamayoP., GaasenbeekM., SturlaL.M., AngeloM., McLaughlinM.E. and KimJ.Y.H., Prediction of central nervous system embryonal tumour outcome based on gene expression, Nature415 (2002), 436-442.
44.
RaymerM.L., PunchW.F., GoodmanE.D., KuhnL.A. and JainA.K., Dimensionality reduction using genetic algorithms, IEEE Transactions on Evolutionary Computation4(2) (2000).
45.
RisingerJ., MaxwellG., ChandramauliG., JazeriA., AprelikovaO. and PattersonT., Microarray analysis reveals distinct gene expression profiles among different histologic types of endometrial cancer, Cancer Research63 (2003), 6-11.
46.
RossD.T., ScherfU., EisenM.B., PerouC.M., ReesC., SpellmanP., IyerV., JeffreyS.S., RijnV.D. and WalthametM., Systematic variation in gene expression patterns in human cancer cell lines, Nature Genetics24 (2000), 227-235.
47.
RuizR., RiquelineJ.C. and Aguilar-RuizJ.S., Incremental wrapper based gene selection from microarray data for cancer classification, Pattern Recognition39(12) (2006), 2383-2392.
48.
SardanaM. and AgrawalR.K., A comparative study of clustering algorithms for relevant gene selection, Advances in Intelligent and Soft Computing166 (2012), 789-797.
49.
SardanaM., AgrawalR.K. and KaurB., Clustering in conjunction with quantum genetic algorithm for relevant genes selection for cancer microarray data, in: Trends and Applications in Knowledge Discovery and Data Mining, Springer Berlin Heidelberg, (2013), 428-439.
50.
SardanaM., AgrawalR.K. and KaurB., An incremental feature selection approach based on scatter matrices for classification of cancer microarray data, International Journal of Computer Mathematics92(2) (2015), 277-295.
51.
SchaathunH.G., Machine learning in image steganalysis, John Wiley and Sons, 2012.
52.
SharmaA., ImotoS. and MiyanoS.A., Top-r feature selection algorithm for microarray gene expression data, IEEE/ACM Trans Comput Biol Bioinforma9(3) (2012).
53.
SharmaA., PaliwalK.K., ImotoS., MiyanoS., SharmaV. and AnanthanarayananR., A feature selection method using fixed-point algorithm for DNA microarray gene expression data, International Journal of Knowledge Based and Intelligent Engineering Systems, NA, (2013).
54.
ShirahataM., KoizumiK. and SaitoS., Gene expression based molecular diagnostic system for malignant gliomas is superior to histological diagnosis, Clinical Cancer Research13 (2007), 7341-7356.
55.
SinghD., FebboP., RoseK., JacksonD., ManolaJ., LaddC. et al., Gene expression correlates of clinical prostate cancer behavior, Cancer Cell1 (2002), 203-209.
56.
SongQ., NiJ. and WangG., A fast clustering-based feature subset selection algorithm for high-dimensional data, Knowledge and Data Engineering, IEEE Transactions on25(1) (2013), 1-14.
57.
TibshiraniR., HastieT., NarasimhanB. and ChuG., Diagnosis of multiple cancer types by shrunken centriods of gene expression, Proceedings National Academy of Science, USA, 99 (2002), 6567-6572.
58.
TangY., ZhangY. and HuangZ., Development of two-stage SVM-RFE gene selection strategy for microarray expression data analysis, IEEE/ACM Transactions on Computational Biology and Bioinformatics4(3) (2007), 365-381.
59.
Van't VeerL., DaiH., Van de VijverM., HeY., HartA. and MaoM., Gene expression profiling predicts clinical outcome of breast cancer, Nature415 (2002), 530-536.
60.
VapnikV., The nature of statistical learning theory, New York: Springer-Verlang, 1995.
61.
WangA., AnN., ChenG., LiL. and AlterovitzG., Accelerating wrapper-based feature selection with K-nearest-neighbor, Knowledge-Based Systems (2015).
62.
WangX., YangJ., TengX., XiaW. and RichardJ., Feature selection based on rough sets and particle swarm optimization, Pattern Recognition Letters28 (2007), 459-471.
63.
WangY. and MakedonF., Application of relief-F feature filtering algorithm to selecting informative genes for cancer classification using microarray data, Computational Systems Bioinformatics Conference (2004), 497-498.
64.
XiaoJ., YanY., LinY., YuanL. and ZhangJ., A Quantum-inspired genetic algorithm for data clustering, IEEE Congress on Evolutionary Computation (CEC) (2008).
65.
XingE., JordanM. and KarpR., Feature selection for high-dimensional genomic microarray data, in: Proceedings of the Eighteenth International Conference on Machine Learning (2001), 601-608.
66.
XueB., ZhangM. and BrowneW.N., New fitness function in binary particle swarm optimization for feature selection, WCCI, IEEE CEC, (2012).
67.
YangJ. and HonavarV., Feature subset selection using a genetic algorithm, IEEE Intelligent Systems (1998).
68.
YangK., CaiZ., LiJ. and LinG.H., A stable gene selection in microarray data analysis, BMC Bioinformatics7 (2006), 228.
69.
YuH.L., GaoS., QinB. and ZhaoJ., Multiclass microarray data classification based on confidence evaluation, Genetics and Molecular Research11(2) (2012), 1357-1369.
70.
YuJ., YuJ., AlmalA.A., DhanasekaranS.M., GhoshD., WorzelW.P. and ChinnaiyanA.M., Feature selection and molecular classification of cancer using genetic programming, Neoplasia9 (2007), 292-303.
71.
YuL. and LiuH., Redundancy based feature selection for microarray data, in: International Conference on KnowledgeDiscovery and Data Mining, Seattle, Washington, (2004), 22-25.
72.
ZhangG., GuY., HuL. and JinW., A novel genetic algorithm and its application to digital filter design, in: Proc IEEE Intelligent Transportation Systems2 (2003), 1600-1605.
73.
ZhangG., LaizhaoH. and WeidongJ., Quantum computing based machine learning method and its application to radar emitter signal recognition, MDAI LNAI3131 (2004), 92-103.
74.
ZhangG.X. and RongH.N., Parameter setting of quantum-inspired genetic algorithm based on real observation, Lecture Notes in Computer Science4481 (2007), 492-499.
75.
ZhangY., ChrisH.Q. and DingT.L., A two-stage gene selection algorithm by combining reliefF and mRMR, BIBE (2007), 164-171.
76.
ZhuM., JinW., PuY. and HuL., A novel feature extraction approach for radar emitter signals, Industrial Electronics and Applications (2007), 1785-1789.
