MSL: A Measure to Evaluate Three-dimensional Patterns in Gene Expression Data

121E olu iona y Bioin o ma ics 2015:11 In oduc ion Mic oa ay echnology is highly used in biological esea ch en i onmen s due o i s abili y o moni o , o a g ea gene collec ion, he RNA concen a ion le els, hus enabling he s udy o gene ic unc ions o species.1 Bioin o ma ics and da a mining ha e de eloped a as numbe o compu a ional ools ha allow us o analyze da a ob ained using his echnology and o ind new knowledge ha is hidden om human eye- sigh .2,3 One o he mos s udied app oaches is pa e n sea ch in gene exp ession da a. The genes exhibi ing high co ela ion among hei exp ession le els could be in ol ed in simila eg- ula o y p ocesses.4 The ela ionship be ween co ela ion and unc ionali y has been p o ed in se e al s udies as in he s udy by D’haeselee e al.5 Clus e ing echniques a e sui able o pe o ming pa e n sea ch by c ea ing g oups o genes ha exhibi simila exp es- sion pa e ns.6 T adi ional clus e ing algo i hms analyze he whole mic oa ay dimensional space g ouping genes ak- ing in o accoun all expe imen al condi ions.7 Howe e , he ac i i y o genes could only appea unde a pa icula se o expe imen al condi ions, exhibi ing local pa e ns. Disco e - ing hese local pa e ns can be key o disco e gene pa hways, which could be ha d o disco e in o he ways. Fo his eason, he pa adigm o clus e ing echniques mus be modi ied o me hods ha allow local pa e n disco e y in gene exp ession da a.8 Biclus e ing9 add esses his p oblem by elaxing he condi ions and by allowing assessmen only unde a subse o he condi ions o he expe imen , and i has p o ed o be suc- cess ul in inding gene pa e ns.10,11 I a hi d dimension is added o he da ase besides genes and condi ions, such as ime, clus e ing and biclus- e ing esul insu icien . The e is a lo o in e es in empo- al expe imen s because hey allow an in-dep h analysis o molecula p ocesses in which he ime e olu ion is impo - an , o example, cell cycles, de elopmen a he molecula le el, o e olu ion o diseases.12 In his sense, iclus e ing appea s as a echnique going one s ep u he by g ouping genes unde pa icula condi ions and unde pa icula ime poin s,13 hus being capable o managing h ee-dimensional (3D) da a. The e o e, iclus e ing is sui able o he analysis o mic oa ay expe imen s whe e se e al samples a e aken a di e en ime poin s.14 This is o g ea in e es since i allows o a deep analysis o biological p ocesses whe e empo a y de elopmen is impo an . Bo h biclus e ing and iclus e ing a ack NP-ha d p o- blems.15 The e o e, algo i hms based on heu is ics a e well sui ed o manage his kind o p oblem. In his sense, de ining an app op ia e quali y measu e o iclus e s is an impo an and essen ial challenge.16 In his wo k, we p opose a quali y measu e called Mul i Slope Measu e (MSL), which measu es he quali y o a iclus e based on he simila i y among he angles o he slopes o med by each p o ile o med by he genes, condi ions, and imes o he iclus e . MSL: A Measu e o E alua e Th ee-dimensional Pa e ns in Gene Exp ession Da a Da id Gu ié ez-a ilés and c is ina ubio-Escude o Depa men o Compu e Science, Uni e si y o Se ille, Se ille, Spain. Abs Ac : Mic oa ay echnology is highly used in biological esea ch en i onmen s due o i s abili y o moni o he RNA concen a ion le els. The analysis o he da a gene a ed ep esen s a compu a ional challenge due o he cha ac e is ics o hese da a. Clus e ing echniques a e widely applied o c ea e g oups o genes ha exhibi a simila beha io . Biclus e ing elaxes he cons ain s o g ouping, allowing genes o be e alua ed only unde a subse o he condi ions. T iclus e ing appea s o he analysis o longi udinal expe imen s in which he genes a e e alua ed unde ce ain condi ions a se e al ime poin s. These iclus e s p o ide hidden in o ma ion in he o m o beha io pa e ns om empo al expe imen s wi h mic oa ays ela ing subse s o genes, expe imen al condi ions, and ime poin s. We p esen an e alua ion measu e o iclus e s called Mul i Slope Measu e, based on he simila i y among he angles o he slopes o med by each p o ile o med by he genes, condi ions, and imes o he iclus e . Keywo ds: iclus e ing, angula compa ison, gene ic algo i hms, i ness unc ion, mic oa ays, ime se ies CiTATion: Gu ié ez-a ilés and ubio-Escude o. msl: a measu e o E alua e h ee- dimensional Pa e ns in Gene Exp ession Da a. E olu iona y Bioin o ma ics 2015:11 121–135 doi: 10.4137/EBo.s25822. RECEi ED: ma ch 11, 2015. RESubMiTTED: may 13, 2015. ACCEPTED oR PubLiCATion: may 21, 2015. ACADEMiC EDiToR: Jike cui, associa e Edi o TYPE: o iginal esea ch unDinG: The au ho s wan o acknowledge he inancial suppo gi en by he Spanish minis y o science and echnology wi h p ojec in2011-28956-c02-02 and Jun a de Andalucía wi h p ojec TIC-7528. The au ho s con i m ha he unde had no in luence o e he s udy design, con en o he a icle, o selec ion o his jou nal. CoMPETinG inTERESTS: Au ho s disclose no po en ial con lic s o in e es . CoRRESPonDEnCE: [email p o ec ed]s, c ubioescude [email protected] CoPYRiGhT: © he au ho s, publishe and licensee libe as academica limi ed. his is an open-access a icle dis ibu ed unde he e ms o he c ea i e commons cc-By-nc 3.0 license. Pape subjec o independen expe blind pee e iew by minimum o wo e iewe s. all edi o ial decisions made by independen academic edi o . upon submission manusc ip was subjec o an i-plagia ism scanning. P io o publica ion all au ho s ha e gi en signed con i ma ion o ag eemen o a icle publica ion and compliance wi h all applicable e hical and legal equi emen s, including he accu acy o au ho and con ibu o in o ma ion, disclosu e o compe ing in e es s and unding sou ces, compliance wi h e hical equi emen s ela ing o human and animal s udy pa icipan s, and compliance wi h any copy igh equi emen s o hi d pa ies. his jou nal is a membe o he commi ee on Publica ion E hics (coPE). Published by libe as academica. lea n mo e abou his jou nal. Gu ié ez-A ilés and Rubio-Escude o 122 E olu iona y Bioin o ma ics 2015:11 We show he esul s ob ained applying he MSL mea- su e embedded in he T iGen Algo i hm,17 an algo i hm based on an e olu iona y heu is ic, gene ic algo i hms. The da ase s used a e a syn he ic da ase and h ee eal expe i- men da ase s: he yeas cell cycle– egula ed genes,18 mouse degene a ion o e inal cells,14 and human ansc ip ion ac o oncogene OTX2 silencing e ec on D425 medulloblas oma cell line.19 The esul s ha e been alida ed by h ee di e en me h- ods. Fi s , by analyzing he co ela ion among he genes, condi ions, and imes in each iclus e using wo di e en co ela ion measu es (Pea son20 and Spea man21). Second, by a g aphic alida ion o he pa e ns ex ac ed based on he g aphic ep esen a ion (see G aphic Rep esen a ion subsec- ion), and hi d we ha e p o ided unc ional anno a ions o he genes ex ac ed om he Gene On ology (GO) p ojec .22 The esul s ob ained ha e been compa ed o wo p e iously de ined quali y measu es, MSR3D23 and LSL,24 showing imp o emen in he pe o mance o he measu e (see Resul s and Discussion sec ion). The es o he a icle is s uc u ed as ollows. A e iew o he la es ela ed wo ks can be ound in S a e o he A sec- ion. Me hods sec ion desc ibes he MSL measu e as well as a b ie desc ip ion o T iclus e ing, he g aphic ep esen a ion applied, and he T iGen algo i hm. In he Resul s and Dis- cussion sec ion, we show he esul s and discussion o apply- ing T iGen o he syn he ic and eal da ase s. The las sec ion shows he conclusions. s a e o he A This sec ion is o p o ide a gene al o e iew o ecen wo ks in he ield o gene exp ession empo al da a. In pa icula , o hose wo ks ela ed o he applica ion o iclus e ing, we ocus on he measu es applied o e alua e he iclus e s. We i s p esen he au ho s’ p e ious con ibu ions o his ield. In ou s udy,23 we desc ibed MSR3D, an adap a- ion o he Mean Squa e Residue (MSR)9 o he 3D space, so ha a hi d ac o , ime in his case, can be aken in o accoun . MSR3D measu es he homogenei y o a iclus e in he ela ion o each alue o he iclus e , wi h he a e age o all genes, a e age o all condi ions, a e age o all imes, a e age o all genes and condi ions, a e age o all genes and imes, a e age o all condi ions and imes, and a e age o all genes, condi ions, and imes in he iclus e . We also ha e p esen ed LSL in ou ecen s udy,24 which measu es he quali y o a iclus e based on he simila i y among he slopes o he angles o med by he leas squa e lines om each o he p o iles o med by he genes, condi ions, and imes o he iclus e . LSL has ob ained be e esul s han MSR3D applied o he same da ase s along wi h he T iGen algo i hm.24 Rega ding o he au ho s’ con ibu ions, in 2005, Zhao and Zaki25 in oduced he iClus e algo i hm o ex ac pa e ns in 3D gene exp ession da a. They p esen ed a measu e o assess iclus e s’s quali y based on he sym- me y p ope y. This allows o e y e icien clus e mining since clus e s a e sea ched o e he dimensions wi h he leas ca dinali y. g- iClus e , an ex ended and gene alized e sion o Zhao and Zaki’s p oposal, was published one yea la e .26 The au ho s claimed ha he symme y p ope y is no sui able o all pa e ns p esen in biological da a and p oposed he Spea man ank co ela ion21 as a mo e app op ia e iclus e e alua ion measu e. An e olu iona y compu a ion p oposal was made by Liu e al.27 The i ness unc ion de ined is a mul iobjec i e measu e ha ies o op imize h ee con lic ing objec i es: clus e s size, homogenei y, and gene-dimension a iance o he 3D clus e . LagMine was in oduced by Xu e al.28 o ind ime- lagged 3D clus e s, wha allows in u n o ind egula o y ela ionships among genes. I is based on a no el 3D clus e model called S2 D3 Clus e . They e alua ed hei iclus e s on homogenei y, egula ion, minimum gene numbe , sample subspace size, and ime pe iods leng h. Wang e al.29 p oposed a new algo i hm called s-clus e basing hei de ini ion o cohe en iclus e s also on inding egula o y ela ionships among genes. Fo ha pu pose, ime shi ing is also conside ed among ime poin s in he e alua ed iclus e s. A new s a egy o mine 3D clus e s in eal- alued da a was in oduced by Sim e al.30 The au ho s de ined he Co ela ed 3D Subspace Clus e s (CSCs), whe e he alues in each clus e mus ha e high co-occu ences and hose co-occu ences a e no by chance. They measu e he clus e s based on he co - ela ion in o ma ion measu e, which akes in o accoun bo h p e equisi es. Hu and Bha naga p esen ed an app oach ocusing on he concep o Low-Va iance 3-Clus e ,31 which obeys he cons ain o a low- a iance dis ibu ion o cell alues. The wo k by Liu e al.32 was ocused on inding Tem- po al Dependency Associa ion Rules, which ela e pa e ns o beha io among genes. The ules ob ained a e o ep esen egula ed ela ions among genes. Finally, a b ie su ey on iclus e ing applied o gene exp ession ime se ies was published in 2011.13 The e a e h ee main ea u es ha a iclus e ing algo i hm can pe o m. Acco ding o Mahan a e al.13, hese ea u es a e empo al cohe ence ha makes e e ence o he abili y o he algo i hm o cap u e he cohe ence o di e en genes in a single ime poin ac oss samples while gene a ing he inal iclus e s and he abili y o ind iclus e s wi h nonconsecu i e ime poin s and iclus e wi h a speci ic ype o pa e n (shi - ing, scaling, delayed). g- iClus e ,26 Moga3c,27 LagMine ,28 s-clus e ,29 and Tempo al Dependency Associa ion Rules32 pe o m he empo al cohe ence ea u e and only T iclus e 25 and Moga3c27 pe o m inding iclus e s con aining non- consecu i e ime poin s. T iclus e 25 inds scaling pa e ns, LagMine 28 inds shi ing and scaling pa e ns and s-clus e 29 MSL: 3D pa e ns om gene exp ession. 123E olu iona y Bioin o ma ics 2015:11 ocuses on ime-delayed pa e ns; he es do no ocus on inding a speci ic ype o pa e n. Ano he ea u e examined is he algo i hm ype dis inguishing be ween de e minis ic (T iclus e 25, g- iClus e 26) and nonde e minis ic (Moga3c27) app oaches. Me hods In his sec ion, we desc ibe ou p oposal, he iclus e quali y measu e called MSL ha is based on iclus e ’s angula ea- u es. We will analyze all MSL p inciples and undamen als and how i has been de eloped. This sec ion is s uc u ed as ollows: T iclus e ing sub- sec ion desc ibes he iclus e ing p ocedu e as an e olu ion o i s well-known p edecesso biclus e ing. In he subsec- ion G aphic Rep esen a ion, we in oduce he g aphic ep esen a ion, which is key o unde s anding he MSL measu e. Then, in he subsec ion MSL Measu e, we ana- lyze he co e o ou wo k, he MSL measu e. Finally, in he T iGen Algo i h subsec ion, we b ie ly desc ibe he T iGen algo i hm. iclus e ing. Clus e ing echniques a e applied o ana- lyze gene exp ession da a om mic oa ay expe imen s. The da ase ob ained om he expe imen , D, con ains genes and expe imen al condi ions and clus e ing aims a inding sub- g oups o genes ha sha e a beha io pa e n acco ding o hei exp ession le el. Biclus e ing appea s as an e olu ion o clus e - ing due o i s abili y o mine subg oups o genes and condi ions om he da a se D, whe e he genes exhibi highly co ela ed pa e ns o beha io unde ce ain expe imen al condi ions.9 T iclus e ing eme ges as an e olu ion o biclus e ing, aking in o accoun he empo a y e olu ion o genes unde pa icula expe imen al condi ions. In his way, om a da ase D ob ained om a mic oa ay expe imen , which con ains genes GD, condi ions CD, and ime poin s TD, we de ine i- clus e ing as a echnique ha inds iclus e s TRI1,…,TRIn om D, whe e a iclus e TRI is o mally de ined as TRI = G × C × T, whe e G ⊆ GD, C ⊆ CD, and T ⊆ TD,17 ie, a subse o genes ha con ains in o ma ion ela ed o he beha io o some genes om da ase G unde condi ions C a imes T. Figu e 1 shows a iclus e wi h genes as ows, condi ions as columns, and ime as dep h. G aphic ep esen a ion. In o de o explain he MSL measu e, we de ine he g aphic ep esen a ion o a iclus e TRIxop, wi h x, o, and p being ei he genes G, expe imen- al condi ions C, o ime poin s T, so ha he x elemen s in TRIxop will be on X axis and o elemen s in TRIxop will be he ou lines ep esen ed in as many panels as p elemen s in TRIxop indica es, as can be seen in Figu e 2. To isually analyze he beha io pa e ns o a iclus e TRI, we always conside h ee g aphical iews: • TRIgc (x = G, o = C, p = T): one panel o each ime, genes on he X axis, he exp ession le els on he Y axis, and he lines o condi ions as he ou line. • TRIg c (x = G, o = T, p = C): one panel o each condi ion, genes on he X axis, he exp ession le els on he Y axis, and he ime lines as he ou line. • TRI gc (x = T, o = G, p = C): one panel o each condi ion, imes on he X axis, he exp ession le els on he Y axis, and he genes as he ou line. Wi h TRIgc and TRIg c, we can analyze how each gene exp ession le el a ies h oughou condi ions and imes, espec i ely. TRI gc ep esen s how each gene a ies h ough- ou ime o each condi ion. MsL measu e. A e analyzing he g aphic ep e- sen a ion o a iclus e , we desc ibe ou p oposal: he Mul i Slope Measu e (MSL). MSL measu es he di e - ences among he angles o med by e e y se ies aced on each o h ee g aphic ep esen a ions aking in o accoun TRIgc , TRIg c, and TRI gc (subsec ion G aphic Rep esen- a ion). MSL akes in o accoun he in luence o neigh- bo ing ime poin s. We can obse e an example o TRI gc iew o TRI = G {g1, g4, g7, g10}, C {c2, c5, c8}, T { 0, 2, 11} in Figu e 3. We can see how each ou line o gene o ms a se o angles ( wo o his pa icula example) de ined by each ime poin in he X axis o e e y panel o expe i- men al condi ion. To calcula e he MSL measu e o a iclus e , we i s pe o m h e m ul ian g ula co m p a is o n e m ca l cula i o n . Th e mul iangula compa ison ope a ion o a g aphic ep esen- a ion xop om a iclus e TRI is de ined in Equa ion 1a. We de ine ACmul i o a iclus e ’s g aphic ep esen a ion TRIxop as he a e age o he di e ences ∆ o angles ec o s a opε ang se (Equa ion 1b) o all ou lines o o each panel p (Vmc in Equa ion 1c) and i s equi alen o he es o he panels (Hmc in Equa ion 1d), wi h Nmc being he numbe Condi ions Times Genes igu e 1. iclus e ep esen a ion. Gu ié ez-A ilés and Rubio-Escude o 124 E olu iona y Bioin o ma ics 2015:11 o di e ences made (Equa ion 1e). An angle ec o o an ou line o in a panel p is de ined as a se o angles ha a e o med by he ou line o aking in o accoun e e y da a poin in he X axis (Equa ion 1 ), each ou line will ha e Numbe o X axis icks – 1 angles as you can see in Figu e 3. The di e ence ∆ be ween wo angles ec o a A and a B is de ined as he a e age o he MAX – MIN (MAX being he maximum and MIN he minimum o wo angles a A(i) and a B(i)) o each componen (o angle) i o a A and a B (Equa ion 1g). AC TRIVH N mul ixop mc mc mc () =+ (1a) angse a a a a a a op op op op op op UT AN = {} 11 21 31 12 12 ,,,,,,,…… ( 1 b ) Va a mc op nex op angse =∆ () () ∑, (1c) Ha a mc op onex p angse =∆ () () ∑, (1d) N op op mc =+− () |||| || ||2 2 ** (1e) a aa op ix xx iAX =∀ − ε ,,… 1 (1 ) ∆ () = ∑ () () () − () () () a a MAXa ia iMIN a ia i AB ia a ABAB AB , ,, , ε |||a AB, (1g) The ACmul i e m is based on se e al ope a ions wi h a op angle ec o s. These elemen s ha e been ob ained based on concep o se ies (Equa ion 2a) so ha a se ies Sop o a ou line o o a panel p is a se o pai o alues om he x axis (xi) and exp ession le els (elj) ha o m he ou line. Fo each se ies Sop, he alpha angle α xi is calcula ed as he spin o he a c angen o he slope o he line o med by (xi, eli) and (xnex (i), elnex (i)) poin s (Equa ion 2b). The spin ope a ion o an angle showed in Equa ion 2c is he posi i e equi alen o his angle i i is nega i e. Sxel xel op AX L =< >< > {} 00 ,,,,… (2a) α x nex ii nex ii ispin xx el el =− −                   () () a c an (2b) elL el0 el1el0 el1 el0 el1 elj elL elj elL elj elL elj . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . el0 el1 . . . . . . . . . . . . . . ... ... . oUT o0 o1 o oUT o0 o1 o oUT o0 o1 o oUT o0 o1 o x0x1x1xAX ...... x0x1x1xAX ... ... x0x1x1xAX ...... x0x1x1xAX p0p1pspAN igu e 2. G aphic ep esen a ion o a iclus e . c2 g4 g1 g7 g10 g4 g1 g7 g10 g4 g1 g7 g10 αg αc2 g7 αc2 g4 c5c8 0 2 11 0 2 11 0 2 11 βgαg αc5 g7 αc5 g4 αc5 g1 βgαc8 g10 βc8 g10 βc5 g7αc8 g7 βc8 g7 βc5 g4 αc8 g4βc8 g4 βc5 g1αc8 g1βc8 g1 βc2 g7 βc2 g4 c2 10 c2 10 c5 10 c5 10 igu e 3. angles o TRI gc g aphic iew. MSL: 3D pa e ns om gene exp ession. 125E olu iona y Bioin o ma ics 2015:11 spin i xx xx ii ii () * αα αα =<⇒=+02π (2c) To conclude, he MSL measu e o a iclus e TRI (Equa- ion 3) is he a e age o he angula compa ison o he h ee g aphic ep esen a ions o he iclus e . Following Figu e 3, we show an example o ACmul i(TRI gc ) calcula ion in Figu e 4. Fi s , we a ange he example iclus- e TRI so ha o each condi ion (panel) we ob ain a able wi h one ow pe gene (ou line) and one column pe ime poin (X axis). Second, in o de o ge each a gc (Equa ion 1 ) o angse (Equa ion 1b), we use Equa ion 2b om Sgc se ies and ob ain all angles α xi o a gc ec o s, and hi d, we use Equa- ions 1c and 1d o Vmc and Hmc calcula ions, espec i ely, going h ough he a se in ho izon al and e ical di ec ion. Finally, we use Equa ion 1a o ob ain he ACmul i(TRI gc) alue. We will ha e o epea his p ocess wice mo e, once o each g aphic ep esen a ion TRIgc and TRIg c, o ob ain he MSL measu e acco ding o Equa ion 3. MSLTRI AC TRIACTRI AC TRI mul igc mul ig c mul i () = ()   + () + 1 3 ggc () (3) iGen algo i hm. In his sec ion, we p esen he T iGen (T iclus e ing-Gene ic based) algo i hm,17 whe e he MSL measu e has been embedded in o de o es i s e ec i eness. T iGen applies a bio-inspi ed pa adigm o an e olu iona y heu is ic, gene ic algo i hms, in such a way ha inds a se o iclus e s om gene exp ession da ase s whe e he ime is also a componen aken in o accoun in he expe imen . This me hod mimics he p ocess o na u al selec ion by c ea ing an ini ial popula ion o indi iduals ep esen ing solu ions ha p1 = c2 x1 = 0 1 s 10 515 30 42 100 40 45 85 30 50 20 10 15 35 45 80 20 20 10 10 40 45 70 35 55 80 30 50 70 50 70 30 40 70 80 2 s3 s 1 s2 s3 s 1 s2 s3 s o1 = g1 o2 = g4 o3 = g7 o4 = g10 Hmc = 17.01 ACmul i (TRI gc) = 1.97 Vmc = 42.37 a g a g a g a g o1 = g1 o2 = g4 o3 = g7 o4 = g10 o1 = g1 o2 = g4 o3 = g7 o4 = g10 x2 = 2x3 = 11 x1 = 0x2 = 2x3 = 11 x1 = 0x2 = 2x3 = 11 p2 = c5p3 = c8 = {1.37, 1.5} = {4.9, 5.03} = {1.47, 4.81} = {4.9, 1.47} = {0, 1.47} = {1.47, 4.9} = {4.81, 1.5} = {4.81, 1.37} = {1.47, 4.81} = {1.37, 4.81} = {1.37, 1.37} = {4.81, 0} a g c21 c81 a g c2 4 a gc5 4c8 4 c8 7 c810 a g c2 10 a g c2 7 = 1.78 ∆ (a g , a g ) c21 c2 7 = 3.38 ∆ (a g , a g ) c21 c2 4 = 1.83 ∆ (a g , a g ) c24 c2 7 = 3.53 ∆ (a g , a g ) c27 c2 10 = 1.7 ∆ (a g , a g ) c24 c2 10 = 1.78 ∆ (a g , a g ) c21 c2 10 = 0.06 ∆ (a g , a g ) c51 c5 4 = 3.43 ∆ (a g , a g ) c51 c5 7 = 3.37 ∆ (a g , a g ) c54 c5 7 = 2.45 ∆ (a g , a g ) c51 c5 10 = 2.42 ∆ (a g , a g ) c54 c5 10 = 2.45 ∆ (a g , a g ) c57 c5 10 = 2.4 ∆ (a g , a g ) c81 c8 4 = 0.09 ∆ (a g , a g ) c21 c2 1= 3.32 ∆ (a g , a g ) c24 c5 4 = 1.76 ∆ (a g , a g ) c24 c8 4 = 1.78 ∆ (a g , a g ) c54 c8 4 = 2.4 ∆ (a g , a g ) c510 c8 10 = 1.7 ∆ (a g , a g ) c210 c8 10 = 0.7 ∆ (a g , a g ) c210 c5 10 = 0.78 ∆ (a g , a g ) c21 c8 1 = 0.68 ∆ (a g , a g ) c51 c8 1 = 1.87 ∆ (a g , a g ) c27 c8 7 = 0.09 ∆ (a g , a g ) c57 c8 7 = 1.78 ∆ (a g , a g ) c27 c8 7 = 4.12 ∆ (a g , a g ) c81 c8 7 = 1.71 ∆ (a g , a g ) c84 c8 7 = 1.76 ∆ (a g , a g ) c84 c8 10 = 4.07 ∆ (a g , a g ) c81 c8 10 = 0.04 ∆ (a g , a g ) c87 c8 10 a g c51 a g c5 7 a g c5 10 igu e 4. ACmul i(TRI gc) example. Gu ié ez-A ilés and Rubio-Escude o 126 E olu iona y Bioin o ma ics 2015:11 1. Inpu : The T iGen algo i hm has wo inpu a gumen s: • D: A da ase con aining he gene exp ession alues om a mic oa ay expe imen con aining genes DG, expe imen- al condi ions DC, and imes DT . The e o e, each cell [i, j, k] om D whe e i ∈ DG, j ∈ DC, and k ∈ DT , ep esen s he exp ession le el o he gene i unde he expe imen al condi ion j a ime k. • P: Se o pa ame e s o execu e he algo i hm as desc ibed in Table 1. These pa ame e s con ol he numbe o solu- ions o iclus e s o ind (N), he numbe o gene a ions o execu e (G), he numbe o indi iduals in he popula- ion (I), and he andomness ac o hey a e gene a ed wi h he ini ial popula ion (Ale) as well as weigh s o he selec ion and mu a ion ope a o s (Sel and Mu ), weigh s o con ol he e ec o he MSL measu e (w ), he size o he iclus e s (wg, wc, w ), and weigh s o con ol he o e lap among solu ions (wog, woc, wo ). The pa ame e s ha e been chosen a e an exhaus i e expe imen a ion wi h all possible anks o alues. Each o he pa ame e s has e ec on he iclus e s ound: size, o e lapping, explo a ion e sus exploi a ion o he algo i hm, e c. We now desc ibe he e ec s o each o he pa ame e s. In he execu ion o T iGen, each pa ame e is associa ed o a gene ic ope a o , ha is, G con ols he whole e olu iona y p ocess so an inc ease in he numbe o gene a ions implies a g ea e numbe o ecombina ion o indi iduals. The e o e, an excessi e inc ease in G may a o exploi a ion e sus explo a ion in excess and he algo i hm may e u n solu ions ha all in o a local minimum. I and Ale con ol he ini ial popula ion c ea ion, and when he numbe o indi iduals I is inc eased, a la ge sea ch space o he solu ions is c ea ed so ha an excessi e inc ease can c ea e a sca e sea ch e ec , and he e o e, no e u n good quali y a e c ossed and mu a ed o a numbe o gene a ions, wi h he bes indi iduals in he popula ion being inally selec ed. The MSL measu e has been applied as he i ness unc ion o assess he quali y o he iclus e s o solu ions in he popula- ion. The lowcha o he T iGen algo i hm can be seen in Figu e 5. We now de ine he mos impo an elemen s o he algo i hm such as inpu s, ou pu s, codi ica ion o indi iduals, and gene ic ope a o s. Table 1. T iGen algo i hm pa ame e s. PARAMETER DESCRiPTion Nnumbe o iclus e s ex ac ed Gnumbe o gene a ions Inumbe o indi iduals in he popula ion Ale andomness a e Sel selec ion a e Mu mu a ion p obabili y w Weigh o MSL measu e wgWeigh o he numbe o genes wcWeigh o he numbe o condi ions w Weigh o he numbe o imes wogWeigh o he o e lap among genes wocWeigh o he o e lap among condi ions wo Weigh o he o e lap among imes D, P Ini ial popula ion E alua ion Selec ion C osso e Mu a ion P ocessed gene a ions < G Upda e SOL Solu ions ound < N Ge bes TRI SOL igu e 5. T iGen algo i hm lowcha . MSL: 3D pa e ns om gene exp ession. 127E olu iona y Bioin o ma ics 2015:11 solu ions; an inc ease o he andomness a e Ale in he ini ial popula ion has o be combined wi h he o e lap con ol o make su e ha a wide a ea o he space o solu ions is ini ially co - e ed. Sel con ols he selec ion mechanism, and as a esul , he c osso e and a high Sel c ea es indi iduals wi h a low le el o gene ic ecombina ion, a o ing exploi a ion e sus explo a ion, and i he pa ame e is inc eased in excess, he algo i hm may all in o a local minimum. On he con a y, a high p obabili y o mu a ion Mu a o s explo a ion e sus exploi a ion, and i inc eased in excess, we will end up wi h solu ions in many a eas o he sea ch space bu wi h low quali y le els. w and wo com- bined wi h w con ol he i ness unc ion; w weigh s con ol he numbe o i ems in he solu ions, an inc ease o hese weigh s in ol es a o ing solu ions wi h mo e olume; he inc ease o wo weigh s leads o li le o nono e lapped solu ions, an excessi e inc ease can lead o he loss o in e es ing solu ions. The con en unde Gene ic Ope a o s in he subsec ion T iGen Algo i hm explains all ope a o s and how a pa ame e a ia ion a ec s he execu ion o T iGen. 2. Ou pu : The T iGen algo i hm’s ou pu will be a se o N iclus e s, o mally SOL = {TRI1, TRI2,…, TRIN}. Each TRIi ε SOL is composed o a subse o genes TRIG, condi- ions TRIC, and imes TRIT om he inpu da ase D and has he bes sco e in i s popula ion when e alua ed unde he MSL measu e. 3. Codi ica ion o indi iduals: Each indi idual in he e olu ion- a y p ocess o he T iGen algo i hm ep esen s a iclus e , which is a po en ial solu ion. The e o e, an indi idual is ep esen ed as a subse o genes Gggg ii iF =< > 1,,,, 2 … a subse o condi ions Cccc ii iQ =< > 12 ,,,… , and a subse o ime poin s T ii iw =< > 12 ,,,.… The genes, condi ions, and imes subse s a e ex ac ed om he inpu da ase D. The algo i hm selec s ime poin s as pa o he iclus e bu always keeping hei o de . All gene ic ope a o s a e applied o each indi idual in he popula ion, in each o hese h ee subse s. 4. O e lapping con ol: We ha e designed an o e lapping con ol mechanism o a oid o e lapping among he i- clus e solu ions ob ained. I is called Da a Hie a chy and consis s in main aining he numbe o occu ences o genes, condi ions, and ime poin s o da ase D in each iclus e solu ion om less o mos isi ed in such a way ha , as we will explain in Ini ial Popula ion in he sub- sec ion T iGen Algo i hm, he ini ial popula ion c e- a ion uses his s uc u e o ini ialize popula ion wi h he minimum o e lapping. This Da a Hie a chy is upda ed a e e y gene a ion a new iclus e solu ion is selec ed. 5. Gene ic ope a o s: a. Ini ial popula ion: Wi h he ini ial popula ion me hod, I indi iduals a e gene a ed a ending o he Ale an- domness pa ame e . An Ale pe cen o indi iduals a e c ea ed a andom by wo me hods: hal o he indi- iduals a e pu ely andomly gene a ed, his is, a an- dom subse o genes TRIG, condi ions TRIC, and imes TRIT a e chosen om D and he o he hal is also andomly c ea ed bu con olling ha he alues o he genes TRIG a e con iguous, he alues o he con- di ions TRIC a e con iguous and he imes TRIT a e con iguous as well. The es o he indi iduals a e an- domly c ea ed, bu aking in o accoun he p e iously c ea ed indi iduals o con ol o e lapping o solu ions acco ding o Da a Hie a chy s uc u e (O e lapping Con ol in he subsec ion T iGen Algo i hm). b. Fi ness unc ion: Ou p oposed measu e has been included as he gene ic algo i hm’s i ness unc ion FF(TRI) along wi h he size and he o e lapping con ol. As can be seen in Equa ion 4, MSL has been combined wi h six o he ac o s as a weigh ed a e - age. Th ee o hese ac o s 1|| || 1|| || −− TRI D TRI D G G C C , , and 1|| || −TRI D T T measu e he numbe o genes, con- di ions, and imes o TRI (|TRIG, C, T|) ela i e o he da ase ’s size (|DG, C, T|). MSL is a minimizing i ness unc ion, and we ha e o se 1 minus each amoun p opo ion in o de o a o TRI wi h g ea e sizes when wg, wc, o w a e inc eased. The o he h ee membe s RTRI SOL TRISOL RTRI SOL TRISOL G G C C , *,, * () () |||||||| , and RTRI SOL TRISOL T T , * () |||| measu e he epea ed genes, condi- ions, o imes elemen s o TRI in he se o al eady ound solu ions SOL (RG, C, T(TRI, SOL)) p opo - ionally calcula ed supposing all o genes, condi ions, o imes a e epea ed in SOL (|TRIG, C, T|*|SOL|) in o de o a o TRI wi h less o e lapping when wog, woc, o wo a e inc eased. Finally, he main membe MSLTRI () 2π measu es MSL (TRI) p opo ionally calcula ed o i s maximum alue 2π in o de o a o TRI wi h smalle MSL when w is inc eased. A de aul con igu a ion o w , wg, wc, w , wog, woc, and wo consis s in ixing w o 0.8 and dis ibu ing 0.2 among wg, wc, w , wog, woc, and wo . FF TRIwwwwwo wo w wMSLTRI wTRI gc gc g G () =++++ ++ () +− 1 21|| * {* * π||| 1|| || 1|| || D wTRI DwTRI D wo G c C C g T T     + −     +−     +** gg G G g C C RTRI SOL TRISOL wo RTRI SOL TRISOL wo *, **, * () + () + |||| |||| ** , *} RTRI SOL TRISOL T T () |||| (4) Gu ié ez-A ilés and Rubio-Escude o 128 E olu iona y Bioin o ma ics 2015:11 c. Selec ion: Th ee g oups o indi iduals a e andomly selec ed so ed om lowes o highes acco ding o he i ness unc ion, and hen a andom selec ion om he h ee g oups is made. The Sel pa ame e indica es how many o hese indi iduals will pass o he nex gene a ion. The es o he indi iduals un il comple - ing he nex popula ion (I – #Selec ed indi iduals) will be c ea ed based on he c osso e ope a o . d. C osso e : To comple e he nex gene a ion, we c e- a e new indi iduals wi h his ope a o as ollows: wo indi iduals (pa en s, A and B) a e combined o c ea e wo new indi iduals (o sp ings, child1 and child2). The pa en s a e andomly chosen. Thei gene ic ma e ials a e combined by a andom one-poin c oss in he genes TRIG, condi ions TRIC, and ime TRIT and mixing he coo dina es in bo h child en.17 e. Mu a ion: An indi idual can be mu a ed acco d- ing o a p obabili y o mu a ion, Mu . The mu a ion p obabili y is e i ied o e e y indi idual, and i i is sa is ac o y, one ou o nine possible ac ions is aken. These ac ions a e add a new andom gene o TRIG, add a new condi ion o TRIC, o add a new ime poin o TRIT , by emo ing a andom gene, condi ion, o ime, o by changing a andom gene o condi ion o ano he ha is andomly chosen. The elec ion o hese ac ions is also andom. Fo he case o addi ion o a new gene, condi ion, o ime, he ope a o checks whe he he new membe is al eady in he indi idual o no . esul s and discussion In his sec ion, we show he esul s ob ained by applica ion o MSL as a i ness unc ion embedded in he T iGen algo i hm17 (see he subsec ion T iGen Algo i hm). MSL has been applied o ou di e en da ase s: one syn- he ically gene a ed da ase and h ee eal da ase s. The eal da ase s a e ob ained om expe imen s wi h he yeas cell cycle (Saccha omyces ce e isiae),18 an expe imen wi h mice (Mus musculus) called GDS451014 and da a om expe imen s wi h humans (Homo sapiens) called GDS4472.19 The las wo da a se s ha e been e ie ed om Gene Exp ession Omnibus,33 a da abase eposi o y o high- h oughpu gene exp ession da a. All biological expe imen s examine he beha io o genes unde condi ions a ce ain imes. Fo he analysis o he iclus e s ob ained as he esul o he expe imen s, we ha e de eloped a h ee-s ep p ocess based on p o iding in o ma ion ela ed o co ela ion among exp es- sion alues, he g aphic p ope ies o he ep esen a ion o he alues, and biological alida ion. The co ela ion alida ion is based on he Pea son and Filon20 and Spea man21 coe icien s. Fo e e y iclus e , we calcula e he a e age o he co ela ion coe icien s be ween each combina ion o gene, condi ion, and ime o all genes. Fo ins ance, o a iclus e wi h ou genes {1, 4, 8, 10}, wo condi ions {3 and 7}, and h ee imes {1, 3 and 5}, we p o ide he Pea sons and Spea mans co ela ion coe icien a e age o alues a he eigh possible combi- na ions, each ha ing h ee ime poin s: Vg=1, c=3, Vg=1, c=7, Vg=4, c=3, Vg=4, c=7, Vg=8, c=3, Vg=8, c=7, Vg=10, c=3, and Vg=10, c=7. The g aphic p ope ies o he ep esen a ion a e shown as desc ibed in he subsec ion G aphic Rep esen a ion as a way o isually check how he gene pa e ns beha e. Finally, o he biological alida ion, we will show he GO e ms22 ela ed o he iclus e s. We p esen a GO anal- ysis able in which we include he mos ep esen a i e e ms ex ac ed by he On ologize so wa e,34 each e m associa ed o a P- alue ha deno es he ele ance le el o he e m. In his ype o s udies, P- alues a e conside ed as ele an below 0.05 and a e be e when close o 0. Rega ding he GO p ojec , i is a majo bioin o ma ics ini ia i e wi h he aim o s anda dizing he ep esen a ion o gene and gene p oduc a ibu es ac oss species and da abases. The p ojec p o ides an on ology o e ms o desc ibing gene p oduc cha ac e - is ics and gene p oduc anno a ion da a. The on ology co e s h ee domains: cellula componen , he pa s o a cell o i s ex acellula en i onmen ; molecula unc ion, he elemen- al ac i i ies o a gene p oduc a he molecula le el, such as binding o ca alysis; and biological p ocess, ope a ions, o se s o molecula e en s wi h a de ined beginning and end, pe inen o he unc ioning o in eg a ed li ing uni s: cells, issues, o gans, and o ganisms. We ha e compa ed he esul s ob ained o hose om Gu ié ez-A ilés and Rubio-Escude o,23 whe e he i ness unc ion was he MSR3D measu e and also o he esul s in Gu ié ez-A ilés and Rubio-Escude o,24 whe e he i ness unc ion was he LSL measu e. The compa ison has been made in e ms o co ela ion and GO analysis. Fo each eal expe imen , we ha e compa ed he maximum, minimum, and mean Pea son’s and Spea man’s co ela ion index and he maximum, minimum, and mean P- alue o each solu ion conside ed. All expe imen s we e execu ed on a mul ip ocesso machine wi h 64 p ocesso s, In el Xeon E7-4820 2.00 GHz wi h 8-GB RAM memo y. We ha e used Ja a o implemen T iGen algo i hm (and o he ad hoc de elopmen s) and an R amewo k o c ea e g aphics and ge da ase esou ces om GEO.33 We now analyze he esul s ob ained in each o he ou expe imen s. syn he ic expe imen s. Syn he ic da a a e widely used no only o es ing he pe o mance o mic oa ay analyzing echniques14 bu also in mo e gene al da a mining publica- ions.35 I has he ad an age ha he p ocess ha gene a ed he da a is well known and so one is able o judge he success o ailu e o he algo i hm.36 In his wo k, we ha e used an applica ion designed by ou sel es o gene a e he syn he ic da a used in his expe i- men . We ha e execu ed he T iGen algo i hm wi h he MSL MSL: 3D pa e ns om gene exp ession. 129E olu iona y Bioin o ma ics 2015:11 measu e o e a syn he ic da ase composed o 4,000 genes, 30 expe imen al condi ions, and 20 ime poin s whose exp es- sion le els we e andomly gene a ed by a c yp og aphic secu e s anda d lib a y Ma h3 p o ided by Apache Commons.37 In his da ase , we inse ed 10 iclus e s composed o 150 genes, 6 expe imen al condi ions, and 4 ime poin s, whose exp es- sion le els o m a cons an beha io pa e n. These iclus e s a e loca ed in andom posi ions in he da ase . To see he beha io o he MSL measu e applied along wi h T iGen and also wi h he aim o analyzing he e ec o he alue o he pa ame e s in he solu ions, we ha e made execu ions se ing N o 200 and a ying o he con- ol pa a me e s as ollows: G ε {100, 200}, I ε {50, 100}, Sel ε {0.5}, Mu ε {0.2, 0.3}, Ale ε {0.3, 0.5}, wg ε {0.03, 0.05, 0}, wc ε {0, 0.01}, w ε {0,0.01}, wog ε {0.04, 0.05}, woc ε {0,0.03}, and wo ε {0,0.03} (see Inpu in he T iGen Algo i hm sub- sec ion o a de ailed desc ip ion o hese pa ame e s). The algo i hm has been capable o inding be ween 94% and 100% o he inse ed iclus e s. The e we e no alse posi i es o alse nega i es ound. The applica ion o he MSR3D along wi h he T iGen algo i hm in he s udy by Gu ié ez-A ilés and Rubio-Escude o23 was capable o inding 91% o 95% and LSL24 ob ained a ma ching a io be ween 93% and 97% o he iclus e s, so we can see in sligh imp o emen when applying he MSL measu e. yeas elu ia ion expe imen s. Fo his expe imen , we ha e applied he T iGen algo i hm wi h MSL measu e o he yeas (Saccha omyces ce e isiae) cell cycle p oblem,18 speci ically he Elu ia ion expe imen . The yeas cell cycle analysis p ojec ’s goal is o iden i y all genes whose mRNA le els a e egula ed by he cell cycle. The esou ces used a e public and a ailable in h p://genome-www.s an o d.edu/cellcycle/. Da a ha e been no malized as pa o he p ep ocessing. We ha e c ea ed a da a- se Delu3D om he elu ia ion expe imen wi h 7,744 genes, 13 expe imen al condi ions, and 14 ime poin s. Expe imen al con- di ions co espond o di e en s a is ical measu es o he Cy3 and Cy5 channels while ime poin s ep esen di e en momen s o aking measu es om 0 o 390 minu es. The pa ame e con igu a ion used o his expe imen is shown in Table 2. We se G and I alues in o de o ob ain a de aul explo a ion o he solu ion space and Ale, Sel, and Mu p o ide us wi h a high andom ac o in popula ion gene a ion, low eli ism in he nex gene a ion p omo ion, and high mu a ion ac o , espec i ely. We a o solu ions wi h a high numbe o genes se ing wg o 0.05 and solu ions wi h high a iabili y in genes, condi ions, and imes hanks o wog, woc, and wo se o 0.05. These con igu a ions ha e been ob ained as a esul o a deep expe imen al s udy on he Delu3D da ase . Rega ding he co ela ion analysis, we can obse e in Table 3 show Pea son and Spea man’s alues a y be ween [0.95, 0.97] and [0.98, 1], espec i ely, which implies a high co ela ion be ween genes se ies o e e y expe imen al con- di ion h ough ime poin s. These high alues con i m us ha he quali y o he iclus e s ob ained om hese expe imen s is e y high in e ms o co ela ion. We can see he g aphic ep esen a ion o iclus e TRI11 in Figu e 6. Only one ou o he 20 iclus e s ob ained has been ep esen ed o legibili y easons. We can obse e how TRI11 Table 2. T iGen algo i hm con ol pa ame e s o yeas cell cycle da ase . PARAMETER ALuES n20 G150 i200 ale 0.9 sel 0.4 mu 0.9 w 0.8 wg0.05 wc0 w 0 wog0.05 woc0.05 wo 0.05 Table 3. co ela ion esul s o iclus e s om he yeas cell cycle da ase . TRIsol PEARSon SPEARMAn TRI10.97 0.98 TRI20.97 0.99 TRI30.96 0.99 TRI40.96 0.98 TRI50.97 0.99 TRI60.96 0.99 TRI70.96 0.99 TRI80.96 0.98 TRI90.96 0.98 TRI10 0.96 0.99 TRI11 0.96 0.99 TRI12 0.95 0.98 TRI13 0.96 0.98 TRI14 0.96 0.98 TRI15 0.97 1 TRI16 0.96 0.98 TRI17 0.96 0.98 TRI18 0.96 0.99 TRI19 0.96 0.99 TRI20 0.96 0.98