POSTER ABSTRACT
E olu iona y Segmen a ion o Yeas Genome
Daniel Ma eos
Compu e Science Depm . U. o
Se ille
A da. Reina Me cedes s/n 41012
Se ille Spain
+34 954 553 866
[email p o ec ed]
José C. Riquelme
Compu e Science Depm . U. o
Se ille
A da. Reina Me cedes s/n 41012
Se ille Spain
+34 954 552 775
[email p o ec ed]
Jesús S. Aguila -Ruiz
Compu e Science Depm . U. o
Se ille
A da. Reina Me cedes s/n 41012
Se ille Spain
+34 954 553 871
[email p o ec ed]
ABSTRACT
Segmen a ion algo i hms di e om clus e ing algo i hms wi h
ega d o how o deal wi h he physical loca ion o genes h oughou
he sequence. The e o e, segmen s ha e o keep he o iginal
posi ions o consecu i e genes, which is no a cons ain o
clus e ing algo i hms. I has been p o en ha exis unc ional
ela ions among neighbou -genes, so he localiza ion o he
bounda ies be ween hese unc ionally simila g oups o genes has
u ned ou an impo an challenge. In his pape , we p esen an
e olu iona y algo i hm o segmen he yeas genome.
1. INTRODUCTION
Ch omosomes a e o ganized in gene sequences. Each ch omosome
has a a iable numbe o genes ha physically a e loca ed in
consecu i e posi ions. Genome s udy ies o ind he unc ionali y o
e e y gene. Recen esea ches in Gene ics y o disco e he
exis ence o unc ional ela ions among one gene and i s
“neighbou s” wi hin a ch omosome. This p ocess is known as DNA
segmen a ion, and i exis s li le scien i ic li e a u e abou i .
The commonly used echniques wo k wi h DNA sequences ins ead
o nume ical alues associa ed o each gene. Nowadays, he
mic oa ay echniques a e gene a ing g ea amoun s o da a, which
migh be e y use ul o analyze he unc ional p ope ies o genes,
as hey collec a nume ical alue o e e y gene. This ac clea s
he way o new algo i hms ha can handle his so o da a.
In his wo k, we p esen an E olu iona y Algo i hm (EA) o ind
alid segmen s om he yeas genome. Fo he yeas genome s udy,
we ha e a ile wi h he six een ch omosomes (NREG). Each gene is
a ow o he ile.
The ile has h ee columns, and each column ep esen s a genomic
cha ac e is ic unde speci ic condi ions. The objec is ei he
clus e ing consecu i e genes wi h simila p ope ies wi h ega d o
he h ee a iables, o clus e ing consecu i e genes p ope ly
di e en ia ed om adjacen clus e s. Each clus e will be a segmen
o genes, as i will main ain he physical loca ion wi hin he genome.
2. EVOLUTIONARY ALGORITHM
Each indi idual o popula ion is a s a ic a ay o na u al numbe s
wi h size NCOR, and i ep esen s a cu o s collec ion in o yeas
genome. Fi een o hese cu o s co espond o he six een
ch omosomes o yeas genome, and hey a e pe manen s. The
six een cu o s co esponding o cen ome es also a e pe manen s.
These cu o s (NCORFIJ=31) al hough hey can’ be mo ed, hey
ha e been included in all indi iduals, making easie he compu ing
p ocess. Fo example, i a cu o s a ay includes among o he s, he
alues 34, 57, 7, 25 and 80, i means ha he e’s a cu o be ween
he 34 h and he 35 h en y o ile, be ween he 57 h and he 58 h
en y, be ween he 7
h and he 8
h en y, e c. The e o e, he
segmen s comp ise om i s o 7 h gene, om 8 h o 25 h gene, om
26 h o 34 h gene, om 35 h o 56 h gene, e c.
In o de o e i y he quali y o he i ness unc ions, we execu e he
algo i hm wi h he o iginal da a, and wi h andomized e sions. We
can unde s and ha a i ness unc ion is co ec i he esul s
ob ained wi h he andom da a a e in e io o he ob ained wi h he
o iginal da a. In ano he case, we can say ha we ha e an
“a i ac ” (An appa en expe imen al esul ha is no ac ually eal
bu is due o he expe imen al me hods).
The i ness unc ion o he i s expe imen s, calcula ed he median
o each a iable o each segmen , and i maximized he co ela ions
be ween hese medians (Eq. 1).
(
)
( )
U1
1
2
23
2
13
2
12
1
,
max
+
=
=
=
++=
NCOR
k
i
k
i
jiij
medMed
MedMedco el
F
ρ
ρρρ
=
i
k
med median o he k h segmen o he i h a iable
Eq. 1. Fi ness unc ion (in e -median co ela ions)
This i ness unc ion u ned ou o be an a i ac , because he esul s
wi h andom da a we e simila o he esul s wi h he o iginal da a.
Ano he possibili y o he i ness unc ion is o maximize he
di e ence be ween he alues o he a iables o wo consecu i e
segmen s, o each a iable sepa a ely and o all. We can use as
s a is ical he median ( obus agains ou lie s) o he classic
Pe mission o make digi al o ha d copies o all o pa o his wo k o
pe sonal o class oom use is g an ed wi hou ee p o ided ha copies a e
no made o dis ibu ed o p o i o comme cial ad an age and ha
copies bea his no ice and he ull ci a ion on he i s page. To copy
o he wise, o epublish, o pos on se e s o o edis ibu e o lis s,
equi es p io speci ic pe mission and/o a ee.
SAC ’04, Ma ch 14-17, 2004, Nicosia, Cyp us.
Copy igh 2004 ACM 1 -58113-812-1/03/04 …$5.00.
1026
2004 ACM Symposium on Applied Compu ing
a i hme ic a e age o ep esen ing he alue o a a iable. We
ep esen hese unc ions in he equa ions 2 and 3 espec i ely.
o each a iable: 









−= ∑+
=
+
1
1
1
max
NCOR
i
j
i
j
i
jmeme
=
j
i
me median o he i h segmen o he j h a iable
o all a iables: 3212 F++=
Eq. 2. Fi ness unc ion (in e -median di e ences)
The i ness unc ion which maximizes he in e -a e age di e ences
(Eq. 3) has he ad an age o he compu a ional cos o a e age,
which i is smalle han he one o median.










−= ∑+
=
+
1
1
1
max
NCOR
i
j
i
j
i
jxx
=
j
i
xa e age o i h segmen o he j h a iable.
Eq. 3. Fi ness unc ion (in e -a e age di e ences)
We ha e used uni o m c osso e owing o he easy implemen a ion
and o he adap a ion o he p oblem. Tha is, we build a new
indi idual choosing andomly cu o s om one o bo h pa en s. As
well, we applied o he well-know me hods ( ixed leng h one poin
and ixed leng h wo poin s) bu hey made wo se esul s.
The mu a ion ope a o al e s each cu o acco ding o wo
p obabili ies: p1 and p2. The p obabili y p1 con ols i a cu o mus
be modi ied; and he p obabili y p2 con ols i he mu a ion has
esul ed in a eplacemen by a andom cu o in he ange allowed,
o in a ligh change o he exis en cu o .
3. EXPERIMENTS
We show he EA pa ame e s and hei alues o each expe imen .
As well, we used he uni o m c osso e as c osso e ope a o , and
0.4 and 0.2 as p1 and p2 p obabili ies espec i ely.
Fi ness Popula ion
Gene a ions
#Cu o s
Co ela ion 300 50 50
Median 400 200 50
A e age 400 200 50
Table 1. EA pa ame e s
In he es s, we execu ed 20 imes he EA wi h he o iginal and
andom da a on Pen ium IV o 2.4 GH, wi h 512 MB o RAM.
Fi ness O iginal da a Random da a
F1 2.541378498 2.463235855
Table. 2. Example o a i ac o i ness unc ion based
on co ela ions
The i ness unc ion based on co ela ion isn' alid o o measu e
he i ness o segmen a ion, because we can ind e y high in e -
a iable co ela ions wi h any dis ibu ion o genes in ch omosomes.
The ime compu a ion o an execu ion is app oxima ely o 2
minu es and hal .
Va iable O iginal da a Random da a
gc3s 2.982499838 1.934499979
expH 19.699998856 22.200000763
ec_ 13.464997292 6.829999447
All (F2) 42.144832511 40.086082458
Table 3. Fi ness unc ion o in e -median di e ences
I exis s signi ican di e ences be ween he o iginal and andom
da a o wo o he h ee s udied a iables (gc3s and ec _).
These esul s demons a e ha o he wo men ioned a iables in
he i s place, i is possible o ind a segmen a ion whe e he esul s
depend o he o de o he genes, ha is o say, a segmen a ion o
he ch omosome wi h own sense.
The ime o compu a ion is app oxima ely o 4 minu es by execu ion.
Va iable O iginal da a Random da a
gc3s 1.828593254 0.804380655
expH 88.142761230 86.721817017
Rec_ 13.985332489 3.723937988
Table 4. Fi ness unc ion based on a e ages
The main i ue ha we can emphasize o he i ness unc ion based
on a e ages, is ha i s ime o compu a ion is app oxima ely he
ou h pa (a minu e) o he p e ious case. We can see he bes
esul s in he able 4.
4. ADDITIONAL AUTHORS
An onio Ma ín, Depa men o Gene ics o Uni e si y o Se ille,
[email p o ec ed].
5. REFERENCES
[1] B adnam KR, Seoighe C, Sha p PM, Wol e KH. 1999. G+C
con en a ia ion along and among Saccha omyces ce e isiae
ch omosomes. Mol Biol E ol 16: 666-675
[2] K uglyak S, Tang H. 2000. Regula ion o adjacen yeas genes.
T ends Gene 16: 109-111.
[3] Li W, Be naola-Gal a P, Haghighi F, G osse I. 2002.
Applica ions o ecu si e segmen a ion o he analysis o DNA
sequences. Compu e s & Chemis y (genome and
in o ma ics special issue), 26(5): 491-510.
[4] Li W. 2001. New s opping c i e ia o segmen ing DNA
sequences. Physical Re iew Le e s, 86(25): 5815-5818.
[5] Li W. 2001. DNA segmen a ion as a model selec ion p ocess.
RECOMB01: P oceedings o he Fi h Annual
In e na ional Con e ence on Compu a ional Biology, pp.
204-210. ACM P ess.
1027