Mining Quantitative Association Rules in Microarray Data Using Evolutive Algorithms

MINING QUANTITATIVE ASSOCIATION RULES IN MICROARRAY DATA USING EVOLUTIVE ALGORITHMS M. Ma ´ınez-Balles e os, C. Rubio-Escude o, J. C. Riquelme Depa men o Compu e Science, Uni e si y o Se ille, Se ille, Spain [email p o ec ed], c ubioescude [email p o ec ed], [email p o ec ed] F. Ma ´ınez- ´ Al a ez Depa men o Compu e Science, Pablo de Ola ide Uni e si y o Se ille, Se ille, Spain ma a[email p o ec ed] Keywo ds: Da a mining, E olu iona y algo i hms, Quan i a i e associa ion ules, Mic oA ay. Abs ac : The mic oa ay echnique is able o moni o he change in concen a ion o RNA in housands o genes si- mul aneously. The in e es in his echnique has g own exponen ially in ecen yea s and he di icul ies in analyzing da a om such expe imen s, which a e cha ac e ized by he high numbe o genes o be analyzed in ela ion o he low numbe o expe imen s o samples a ailable. In his pape we show he esul o apply- ing a da a mining me hod based on quan i a i e associa ion ules o mic oa ay da a. These ules wo k wi h in e als on he a ibu es, wi hou disc e izing he da a be o e. The ules a e gene a ed by an e olu iona y algo i hm. 1 INTRODUCTION The use o massi e p ocessing echniques has e olu- ionized he bio echnology esea ch and i has highly inc eased he amoun o da a ob ained(Du bin e al., 1998). In pa icula , mic oa ay echnology has e o- lu ionized he biological esea ch due o i s abili y o moni o changes in RNA concen a ion in housands o genes simul aneously (Du bin e al., 1998). Re- sea ch in molecula biology has adi ionally ocused on he s udy gene o gene, bu nowadays we a e in he genomic e a and genes a e s udied in housands o e en whole genomes. Besides he genes, i is neces- sa y o know he ela ionships be ween hem. In his con ex we p esen he esul o applying a da a mining echnique, speci ically, associa ion ules, o gene exp ession da a om expe imen s using mi- c oa ay echnology. The aim o his p ocess o min- ing associa ion ules is o disco e he p esence o pai s (a ibu e - alue), which appea in a da ase wi h a ce ain equency. This echnique is applied o disco e associa ions be ween genes om mic oa ay da ase s, in which gene exp essionis linked o ano he gene exp ession, Gen1⇒Gen2. The e a e many e icien algo i hms o ind hese ules, mos ocused on disc e e da a. Howe e in he eal wo ld, pa icula ly in he p oblem o deal in his pape , da ase s consis s o con inuous a ibu es. In addi ion, he ools ha wo k in con inuous domains jus disc e ize he a ibu es using a speci ic s a egy and ea hese a ibu es as i heywe e disc e e (Van- nucci and Colla, 2004). In his pape , he esul o applying a gene ic algo i hm (GA) is p esen ed. The algo i hm can ind associa ion ules in da abases wi h con inuous a ibu es om mic oa ay da a, a oiding he disc e iza ion as a s ep in he p ocess. The esul s will show ha he ules ob ained ha e been able o success ully cha ac e ize he da a unde lyingand also o g oup ele an genes o he p oblem s udied. The es o he pape is di ided as ollows. Sec- ion 2 p o ides he me hodology used in his wo k. The esul s ob ained by he algo i hm de eloped a e discussed in Sec ion 3. Finally, Sec ion 4 desc ibes he achie ed conclusions. 2 METHODOLOGY 2.1 Sea ch o Rules This wo k is ocused on a con inuous domain. I is necessa y o g oup he se s o alues in in e als o be able o exp ess he membe ship o he alues o each 574 g oup. Ranges ha e no been ixed o in e als. The Gene ic Algo i hm inds and adjus he mos app o- p ia e in e als o ind quan i a i e associa ion ules. Each indi idual in he popula ion is a ule. The se o ules comp ising he popula ion unde go an e olu- iona y p ocess in which mu a ion and c osso e op- e a o s will be applied. The indi idual wi h he bes i ness a he end o he p ocess ep esen s he bes ule. The use can d i e he sea ch p ocess because he i ness unc ion has been p o ided wi h a se o pa ame e s. Ou p oposal pe o ms an IRL p ocess (I e a i e Rule Lea ning) (Ven u ini, 1993) o penal- ize ins ances al eady co e ed by ules in o de o em- phasize he co e ing o ins ances s ill no co e ed. In he ollowing sec ions we p o ide de ails o he gene al scheme o he algo i hm, he i ness unc ion, ep esen a ion o indi iduals and gene ic ope a o s. 2.2 Scheme o he Algo i hm Fi s , he ules popula ion is ini ialized and e alua ed. All ules a e e alua ed acco ding o equa ion 1. Thus, in each i e a ion heselec ion ope a o is applied ose- lec he bes ules on he basis o he i ness unc ion. Then, he c osso e ope a o is applied o he selec ed ules while he popula ion size is no comple ed. In- di iduals a e andomly selec ed acco ding o pmu in o de o apply he mu a ion ope a o . Finally, he new popula ion is again e alua ed by he i ness unc ion and he e olu i e p ocess es a s. No e ha he p o- cess will be epea ed as many imes as he maximum numbe o p ese gene a ions indica es. 2.3 Indi iduals Codi ica ion The lowe and uppe limi s o he in e als o each a ibu e will be ep esen ed by he di e en genes o an indi idual. Because he a ibu es a e con inuous, indi iduals a e ep esen ed by an eal coding. An in- di idual consis s o a no ixed numbe o a ibu es less han n, which ep esen s he numbe o a ibu e in he da abase. The ep esen a ion o an indi idual consis s in wo da a s uc u es as shown in Figu e 1. The uppe s uc- u e includes all he a ibu es o he da abase, whe e ijis he lowe limi o he ange and sjis he uppe limi . The bo om s uc u e indica es he membe ship o an a ibu e o he ule ep esen ed by a indi idual. The ype o each a ibu e j, can ha e h ee alues: 0 when he a ibu e does no belong o he ule, 1 i i belongs o he an eceden o he ule and 2 when i be- longs o he consequen pa . I an a ibu e is wan ed o be e ie ed o a speci ic ule, i can be done by modi ying he alue equal o 0 o he ype by a alue equal o 1 o o 2 depending on he an eceden o con- sequen . Figu e 1: Rep esen a ion o an indi idual o he popula ion. An example o one indi idual o he popula ion is shown in Figu e 2. A1∈[20.1, 23.5] and A2∈[10.3, 15.8] =⇒A4∈ [54.4, 59.6]. Figu e 2: Example o an indi idual o he popula ion. 2.4 Ini ial Popula ion The numbe o a ibu es o each indi idual is an- domly chosen o gene a e he ini ial popula ion ak- ing in o accoun he desi ed o ma o he ules. In addi ion, he minimum and maximum numbe s in he an eceden s and consequen s, he minimum and max- imum numbe o a ibu es ha belong o ule ep e- sen ed by an indi idual a e con olled. 2.5 Gene ic Ope a o s The gene ic ope a o s implemen edin he p opose ge- ne ic algo i hm a e: Selec ion, C osso e and Mu a- ion. •Selec ion. An eli is s a egy eplica ing he indi- idual wi h bes i ness and a oule e selec ion- based me hod o he emaining indi iduals ac- co ding o hei i ness a e used . •C osso e . Two pa en s a e chosen by he oule e selec ion-based me hod and hey a e combined o gene a e a new indi idual. The ype o all he el- e an a ibu es in bo h pa en s a e analyzed. I bo h pa en s ha e an equal ype o he same a ibu e, i will assigned o o sp ing. The in e al is ob ained as a andom alue be ween he limi s o he in e als o bo h pa en s. Ne e heless, i bo h pa en s ha e a di e en ype o he same a ibu e, one o he wo pa en s is andomly chosen and o sp ing ha e he in e als and ype a ibu e o he selec ed pa en . •Mu a ion. Indi iduals o he popula ion a e an- domly selec ed in o de o apply he mu a ion de- MINING QUANTITATIVE ASSOCIATION RULES IN MICROARRAY DATA USING EVOLUTIVE ALGORITHMS 575 pending on a mu a ion p obabili y pMu . The mu- a ion p ocess consis s in modi ying indi iduals genes, acco ding o a p obabili y pMu Gen in he indi idualsselec ed. The mu a ion can be ocused on he a ibu e ype o on he in e als, in which a e possible h ee sepa a e cases: mu a ion o he uppe limi , lowe limi o bo h limi s o he in e - al. Fo his aim, a andom alue be ween 0 and 10% o he o al domain in he a ibu e is gene a ed and i is added o sub ac ed o he limi o he in e al andomly selec ed. 2.6 Fi ness Func ion The i ness unc ion calcula ion in ol es se e al mea- su es ha gi e us in o ma ion abou he ules. In pa - icula , he mos ep esen a i e a e he suppo and con idence ha will posi i ely a ec he ule. How- e e , i is necessa y o ake in o accoun a numbe o ac o s wi h nega i e a ec in he quali y o he ule. In he ampli ude o he in e als, he algo i hm may y o ex end he in e als o comple e he domain o each a ibu e. Fo his aim, i is necessa y o include a measu e limi ing g ow h o he in e als du ing he e olu i e p ocess. The e alua ion unc ion should be maximized in he e olu iona y p ocess is gi en by he equa ion . I consis s in se e al pa ame e s which alues a e cal- cula ed om he indi idual mul iplied by a weigh o calib a e he e ec o each pa ame e in he o e all e alua ion. (i) = ws·sup+wc·con −w · eco (1) +wn·nA ib−wa·ampl whe e sup is he suppo , con is he con idence, eco is he numbe o eco e ed ins ances, nA ib is he numbe o a ibu es in he ule, ampl is he a - e age size o in e als o he a ibu es belong o he ule and ws,wc,w ,wnand waa e weigh s in o de o d i e he p ocess o sea ch o ules. The meaning o each pa ame e s in he equa ion is: •Suppo (sop). Pe cen age o eco ds in he da ase co e ed by he ule. •Con idence (con ). Condi ional p obabili y o consequen gi en he an eceden . Con idence is calcula ed di iding he suppo o he ule and he suppo o he an eceden . •Numbe o Reco e ed Ins ances ( ecub). I is used o indica e a sample has al eady been co - e ed by a p e ious ule. Rules co e ing di e en egions o sea ch o space a e p e e ed. •Numbe o A ibu es (na ib). Numbe o a - ibu es (genes) belong o he ule (indi idual). •Ampli ude (ampl). A e age o in e als size o he a ibu es belong o he ule. 3 RESULTS The esul s o applying he algo i hm p oposed in Sec ion 2 o a da ase acqui ed om a mic oa ay expe imen ela ed o in lamma ion and immune e- sponse a e p esen ed. In lamma ion is a c i ical p o- cess because he human body uses o p o ec i - sel om in ec ions and lesions. In his expe i- men , conduc ed a he Uni e si y o S . Louis, Mis- sou i(Cal ano e al., 2005), he blood o eigh olun- ee s is analyzed, ou ea ed wi h a oxin p oduces an in lamma o y p ocess and 4 wi h placebo. Sam- ples has been aken a 6 ime poin s o e 24 hou s, ob aining a o al o 48 mic oa ays. The algo i hm was es ed wi h he ollowing pa- ame e s o AG: 100 o he size o he popula ion, 100 o he numbe o gene a ions, 20 o he num- be o ules o ob ain, 0.8 o he mu a ion p obabili y pMu o he indi iduals and 0.2 o he mu a ion p ob- abili y pMu Gen o each gene in he indi idual. The i - ness unc ion weigh s a e: 1 o ws, 0.5 o wc, 0.3 o w , 0.1 o wn, and 0.1 o wa. The eason o assign a high alue o he weigh wsis o co e he maxi- mum numbe o examples ob ained by he ules. The weigh associa ed o he ins ances co e ed by o he ules and he size o he in e als a e se o penalize ules whose in e als a e oo la ge and co e ing ex- amples al eady co e ed by o he ules. The algo i hm has been execu ed 10 imes, and only hose ules ha co e a minimum o 6 samples ou o 48 (suppo 12.5 %) ha e been aken in o ac- coun , ob aining a o al o 76 ules o he 200 possible ules (10 execu ions x 20 ules in each un). The limi o he suppo has been se a ha alue because 6 samples shows da a om a comple e olun ee , and such low limi o he suppo has been chosen be- cause in his ype o expe imen s we a e in e es ed bo h in equen ela ions, bu also in he no so e- quen ones (McIn osh and Chawla, 2007). The a e age suppo ob ained o he 151 ules has been 47.17% wi h a con idence close o 100% o mos o hem. The a e age ampli ude o in e als in he ules was 24.7%, which jus i ies he use o quan i- a i e ules in place o he classical ules in which he whole domain o he a ibu e is aken in o accoun . The ules ob ained ha e accu a ely cha ac e ized da ase ea ed, ha ing wo ypes o ules: hose wi h a suppo alue be ween 75 % and 100 %, and hose ICAART 2011 - 3 d In e na ional Con e ence on Agen s and A i icial In elligence 576 Table 1: Analyzed Rules. Id Rule Sup. (%) Con . (%) Ampl. (%) 1 215091 s a ∈[98.35 , 376.99] and 215760 s a ∈[527.04 , 1168.82] 52 100 17 =⇒203944 x a ∈[890.80 , 5308.61] 2 205119 s a ∈[783.83 , 1527.60] and 215597 x a ∈[8301.78 , 9819.85] 20 100 16 =⇒212967 x a ∈[2076.59 , 2592.60] 3 222099 s a ∈[859.491 , 1425.210] 55 100 17 =⇒49327 a ∈[1517.45 , 2239.45] wi h suppo alues less han 50 % whe e in almos cases co e eco ds o endo oxin- ea ed g oup o placebo g oup. The numbe o ules co e ing he placebo g oup is signi ican ly highe , which makes sense because his g oup has gene exp ession aluesmo e s able and e- quen han he g oup ea ed wi h endo oxin(Rubio- Escude o, 2007). To examine he ele ance o he ules ob ained in he s udied p oblem, we ha e used he On o-CC so wa e (Rome o-Zliz e al., 2008), which e ie es in o ma ion ega ding he unc ional- i y o a se o genes ha is passed as a que y, and a PI alue ( he p obabili y o in e sec ion) associa ed wi h he ele ance o hese genes appea oge he in one ule. PI is a alue o minimize be ween 0 and 1 and conside ed ele an hose ob ained unde 0.05. The esul s o only 3 ules a e lis ed in Table 1 o eadabili y. When On o-CC is applied, he PI alues ob ained o e e y ule a e qui e low, indica ing he ele ance o g ouping hese h ee genes wi h espec o hese e ms, immune esponse and ela ed e ms a e explici ly included. 4 CONCLUSIONS In his pape we p esen he esul o applying an e o- lu i e echnique o ex ac ing associa ion ules om mic oa ay da a. We ha e seen he ules ob ained a e able o success ully cha ac e ize he da ase applied, ei he co e ing almos all samples, o co e ing sam- ples only one o he wo g oups in he da a: ea ed wi h endo oxin o ea ed wi h placebo. In addi ion, he mean ampli ude o he in e als was 24.7%, which jus i ies he use o quan i a i e ules in place o he classical ules. We ha e shown he ele anceo he ules ob ained o he p oblem s udied using he On o-CC p og am. The PI alues ob ained show signi icance in he g oup o genes ound in he ules, and secondly he e ms ob ained que ying Gene On ology a e closely ela ed o he p oblem o in lamma ion. Thus, we conclude ha he use o quan i a i e as- socia ion ules, in pa icula hose ob ained by he algo i hm p oposed, is a alid me hod o analyzing mic oa ay da a, and we conside i a s a ing poin o u u e wo k, applying his echnique o o he mi- c oa ay da a, compa ing wi h o he analy ical ech- niques and seeing he impo ance o he in luence an eceden -consequen ob ained by he ules wi h e- ga d o gene ic ne wo ks. ACKNOWLEDGEMENTS The inancial suppo om he Spanish Minis y o Science and Technology, p ojec TIN 2007-68084-C- 02, and om he Jun a de Andaluca, p ojec P07-TIC- 02611, is acknowledged. REFERENCES Cal ano, S. E., Xiao, W., Richa ds, D. R., Felciano, R. M., Bake , H. V., Cho, R. J., Chen, R. O., B owns ein, B. H., Cobb, J. P., Tschoeke, S. K., Mille -G aziano, C., Moldawe , L. L., Mind inos, M. N., Da is, R. W., Tompkins, R. G., Low y, S. F., and La ge Scale Collab Res P og am, I. A. (2005). A ne wo k-based analysis o sys emic in lamma ion in humans. Na u e, 437. Du bin, R., Eddy, S., K ogh, A., and Mi chison, G. (1998). Biological Sequence Analysis: P obabilis ic Models o P o eins and Nucleic Acids. Camb idge Uni e si y P ess. McIn osh, T. and Chawla, S. (2007). High-con idence ule mining o mic oa ay analysis. IEEE/ACM T ansac- ions on Compu a ional Biology and Bioin o ma ics, 4(4):611–623. Rome o-Zliz, R., del Val, C., Cobb, J., and Zwi , I. (2008). On o-cc: a web se e o iden i ying gene on ology concep ual clus e s. Nucleic Acids Res, 36(4):W352– W357. Rubio-Escude o, C. (2007). Fusion o Knowledge owa ds Iden i ica ion o Gene ic P o iles in he Sys emic In- lamma ion P oblem. Ph.D Thesis. Un e sidad de G anada. Vannucci, M. and Colla, V. (2004). Meaning ul disc e iza- ion o con inuous ea u es o associa ion ules min- ing by means o a som. In P oceedings o he Eu o- pean Symposium on A i icial Neu al Ne wo ks, pages 489–494. Ven u ini, G. (1993). SIA: a Supe ised Induc i e Algo- i hm wi h gene ic sea ch o lea ning a ibu e based concep s. In P oceedings o he Eu opean Con e ence on Machine Lea ning, pages 280–296. MINING QUANTITATIVE ASSOCIATION RULES IN MICROARRAY DATA USING EVOLUTIVE ALGORITHMS 577