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