Page 28 - Fister jr., Iztok, and Andrej Brodnik (eds.). StuCoSReC. Proceedings of the 2017 4th Student Computer Science Research Conference. Koper: University of Primorska Press, 2017
P. 28
Slika 3: Primer izraˇcuna sume parov na treh sekven-
cah.
Za uspeˇsno poravnavo sekvenc je potrebno imeti sekvence
enakih dolˇzin. Zaradi mutacij zelo pogosto to ni moˇzno, kar
smo reˇsili z vstavljanjem vrzeli. Dolˇzino sekvenc smo zato
doloˇcili po enaˇcbi:
L = lmax × (1 + rsp) (1)
kjer lmax predstavlja najdaljˇso sekvenco in rsp skalirni fak-
tor, s katerim poveˇcamo dolˇzino sekvenc [7]. rsp je pozitivno
ˇstevilo za katerega je priporoˇcena vrednost 0,2 [7]. Doloˇciti
primerno dolˇzino sekvenc je pomembno, ker se v primeru
premajhne vrednosti lahko zgodi, da ne najdemo optimalne
reˇsitve pri sekvencah s slabˇso podobnostjo, in nasprotno,
pri predolgih sekvencah prevelik iskalni prostor lahko po-
meni, da bo iskanje optimalne reˇsitve lahko trajalo veliko
dlje ˇcasa [7]. Vsako sekvenco nakljuˇcno zapolnimo z vrzelmi
tako, da bo imela dolˇzino L.
Slika 2: Potek evolucijskega algoritma. Lokacije vrzeli smo generirali podobno kot v [3], s tem da
smo v vsaki sekvenci ustvarili permutacijo L ˇstevil za vsako
SP C(i) = eval(Sp,i, Sq,i) sekvenco. Iz vsake permutacije smo vzeli toliko ˇstevil, kot
je originalna dolˇzina sekvence in jih uredili po naraˇsˇcajoˇcem
1≤p≤q≤k vrstnem redu. Ta ˇstevila predstavljajo lokacije simbolov v
sekvenci. Preostale indekse smo zapolnili z vrzelmi. Cˇ e
• i - oznaka stolpca imamo v kandidatu na primer DNK sekvenco: CTG, kjer je
• p, q - oznaki sekvenc vrednost L enaka 5 in generirano permutacijo: 3, 2, 5, 1, 4;
• k - ˇstevilo vseh sekvenc bo izgled konˇcne sekvence: –CT–G.
• S - sekvenca
Kriˇzanje smo povzeli po [6], kjer se je nakljuˇcnega kandidata
iz populacije z trenutnim lahko kriˇzalo horizontalno ali ver-
tikalno. Tip kriˇzanja je bil izbran nakljuˇcno, moˇznost obeh
kriˇzanj je bila 50 %. Horizontalno kriˇzanje deluje tako, da
smo za vsako vrstico v kriˇzancu nakljuˇcno izbrali sekvenco
iz enega od kandidatov (slika 5). Pri vertikalnem kriˇzanju
smo nakljuˇcno izbrali toˇcko preseka, pri kateri dobi kriˇzanec
vsebino vsake sekvence do toˇcke preseka skopirano od prvega
kandidata in od toˇcke preseka naprej od drugega kandidata
(slika 4). Pri vertikalnem kriˇzanju smo morali paziti, da se
struktura bioloˇskih sekvenc ohrani.
V vsakem stolpcu smo medsebojno primerjali simbole, kjer Mutacijski operator je bil implementiran tako, da smo na-
se je h konˇcni oceni ocenitvene funkcije dodala vrednost po kljuˇcno izbrali sekvenco v kandidatu in poiskali takˇsen sim-
naslednjih kriterijih [7]: bol, ki je imel vsaj eno sosednjo vrzel. Za vsako sosednjo
vrzel izbranega simbola smo zamenjali simbola v indeksih
• 2 v primeru dveh enakih simbolov, sekvence in preverili novo vrednost ocenitvene funkcije. Od
• -2 v primeru dveh vrzeli in vseh moˇznih zamenjav smo izbrali razliˇcico kandidata z naj-
• -1 v primeru vrzeli in simbola. veˇcjo vrednostjo ocenitvene funkcije [3].
Primer uporabe metode sume parov na treh sekvencah pri- V procesu selekcije smo mutiranca zamenjali s trenutnim
kazuje slika 3, kjer je bil konˇcni rezultat ocenitvene funkcije kandidatom v populaciji v primeru, ˇce je bil bolje ovrednoten
suma vseh vrednosti stolpcev. s strani ocenitvene funkcije.
3. EKSPERIMENTI
StuCoSReC Proceedings of the 2017 4th Student Computer Science Research Conference 28
Ljubljana, Slovenia, 11 October
cah.
Za uspeˇsno poravnavo sekvenc je potrebno imeti sekvence
enakih dolˇzin. Zaradi mutacij zelo pogosto to ni moˇzno, kar
smo reˇsili z vstavljanjem vrzeli. Dolˇzino sekvenc smo zato
doloˇcili po enaˇcbi:
L = lmax × (1 + rsp) (1)
kjer lmax predstavlja najdaljˇso sekvenco in rsp skalirni fak-
tor, s katerim poveˇcamo dolˇzino sekvenc [7]. rsp je pozitivno
ˇstevilo za katerega je priporoˇcena vrednost 0,2 [7]. Doloˇciti
primerno dolˇzino sekvenc je pomembno, ker se v primeru
premajhne vrednosti lahko zgodi, da ne najdemo optimalne
reˇsitve pri sekvencah s slabˇso podobnostjo, in nasprotno,
pri predolgih sekvencah prevelik iskalni prostor lahko po-
meni, da bo iskanje optimalne reˇsitve lahko trajalo veliko
dlje ˇcasa [7]. Vsako sekvenco nakljuˇcno zapolnimo z vrzelmi
tako, da bo imela dolˇzino L.
Slika 2: Potek evolucijskega algoritma. Lokacije vrzeli smo generirali podobno kot v [3], s tem da
smo v vsaki sekvenci ustvarili permutacijo L ˇstevil za vsako
SP C(i) = eval(Sp,i, Sq,i) sekvenco. Iz vsake permutacije smo vzeli toliko ˇstevil, kot
je originalna dolˇzina sekvence in jih uredili po naraˇsˇcajoˇcem
1≤p≤q≤k vrstnem redu. Ta ˇstevila predstavljajo lokacije simbolov v
sekvenci. Preostale indekse smo zapolnili z vrzelmi. Cˇ e
• i - oznaka stolpca imamo v kandidatu na primer DNK sekvenco: CTG, kjer je
• p, q - oznaki sekvenc vrednost L enaka 5 in generirano permutacijo: 3, 2, 5, 1, 4;
• k - ˇstevilo vseh sekvenc bo izgled konˇcne sekvence: –CT–G.
• S - sekvenca
Kriˇzanje smo povzeli po [6], kjer se je nakljuˇcnega kandidata
iz populacije z trenutnim lahko kriˇzalo horizontalno ali ver-
tikalno. Tip kriˇzanja je bil izbran nakljuˇcno, moˇznost obeh
kriˇzanj je bila 50 %. Horizontalno kriˇzanje deluje tako, da
smo za vsako vrstico v kriˇzancu nakljuˇcno izbrali sekvenco
iz enega od kandidatov (slika 5). Pri vertikalnem kriˇzanju
smo nakljuˇcno izbrali toˇcko preseka, pri kateri dobi kriˇzanec
vsebino vsake sekvence do toˇcke preseka skopirano od prvega
kandidata in od toˇcke preseka naprej od drugega kandidata
(slika 4). Pri vertikalnem kriˇzanju smo morali paziti, da se
struktura bioloˇskih sekvenc ohrani.
V vsakem stolpcu smo medsebojno primerjali simbole, kjer Mutacijski operator je bil implementiran tako, da smo na-
se je h konˇcni oceni ocenitvene funkcije dodala vrednost po kljuˇcno izbrali sekvenco v kandidatu in poiskali takˇsen sim-
naslednjih kriterijih [7]: bol, ki je imel vsaj eno sosednjo vrzel. Za vsako sosednjo
vrzel izbranega simbola smo zamenjali simbola v indeksih
• 2 v primeru dveh enakih simbolov, sekvence in preverili novo vrednost ocenitvene funkcije. Od
• -2 v primeru dveh vrzeli in vseh moˇznih zamenjav smo izbrali razliˇcico kandidata z naj-
• -1 v primeru vrzeli in simbola. veˇcjo vrednostjo ocenitvene funkcije [3].
Primer uporabe metode sume parov na treh sekvencah pri- V procesu selekcije smo mutiranca zamenjali s trenutnim
kazuje slika 3, kjer je bil konˇcni rezultat ocenitvene funkcije kandidatom v populaciji v primeru, ˇce je bil bolje ovrednoten
suma vseh vrednosti stolpcev. s strani ocenitvene funkcije.
3. EKSPERIMENTI
StuCoSReC Proceedings of the 2017 4th Student Computer Science Research Conference 28
Ljubljana, Slovenia, 11 October
