Page 29 - 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. 29
Tabela 1: Nastavitve algoritma.
Parameter Vrednost
Velikost populacije 60
Dovoljeno ˇst. ovrednotenj 100000
Prostorsko razmerje 0,2
Horizontalno kriˇzanje 0,5
Vertikalno kriˇzanje 0,5
Tabela 2: Nabor podatkov [4].
Ime Sˇt. se- Povpreˇcna dolˇzina Identifikatorji
kvenc (Najkrajˇsa sekv., sekvenc
Najdaljˇsa sekv.)
D1 5 1092 (1006, 1142) M60059, M60060,
M60061, M60062,
M60063
Slika 4: Vertikalno kriˇzanje. D2 6 212 (211, 212) Z75841, Z75850,
Z75854, Z75852,
Z75858, Z75851
D1 in 206 v skupini sekvenc D2.
Tabela 3: Rezultati
Ime Sˇt. ujemajoˇcih Sˇt. ujemajoˇcih
stolpcev z EA stolpcev z Clustal
Omega
D1 43 854
D2 111 206
Slika 5: Horizontalno kriˇzanje. 4. ZAKLJUCˇ EK
Zaradi hitrosti smo algoritem implementirali v jeziku C++. V ˇclanku smo predstavili metodo poravnave sekvenc s po-
Eksperimente smo izvajali na osebnem raˇcunalniku z 16GB moˇcjo evolucijskega algoritma. Z naˇso implementacijo smo
spomina, 2.2GHz Intel Core i7 procesorjem in MacOS ope- uspeli doseˇci poravnavo sekvenc DNK. Algoritem bi lahko
racijskim sistemom. izboljˇsali v procesu mutacije, kjer bi z veˇc razliˇcnimi tipi
mutacij lahko dosegli veˇcjo raznolikost populacije. Potrebno
Uˇcinkovitost algoritma smo primerjali z uveljavljenim pro- bi bilo narediti tudi analizo vrednosti krmilnih parametrov.
gramskim orodjem Clustal Omega, ki spada v druˇzino pro- Npr. z veˇcjo populacijo in daljˇsim evolucijskim procesom bi
gramov Clustal (http://www.ebi.ac.uk/Tools/msa/clustalo/). verjetno dobili boljˇse rezultate. Implementacija bolj kom-
Uspeˇsnost poravnav obeh algoritmov smo ocenili s ˇstevilom pleksne ocenitvene funkcije in generacija zaˇcetne populacije,
polno ujemajoˇcih se stolpcev v poravnavi. Uporabili smo po- ki ni nakljuˇcno generirana, predstavljata tudi dve izboljˇsavi
doben nabor podatkov, kot je bil uporabljen v [4] (tabela 2). za pridobitev boljˇse konˇcne poravnave. Razvoj algoritma se
Sekvence omenjene v [4] smo prenesli iz spletne strani evrop- bo nadaljeval v magistrskem delu, kjer bomo poleg porav-
skega inˇstituta za bioinformatiko (http://www.ebi.ac.uk). nave sekvenc DNK implementirali ˇse zmoˇznost poravnave
proteinov s pomoˇcjo razliˇcnih ocenitvenih matrik. Algori-
V implementiranem programu smo sekvence podali v teks- tem bomo bolj podrobno primerjali z drugimi sorodnimi re-
tovnem formatu FASTA in nastavili parametre, kot jih pri- ˇsitvami na veˇcjem naboru podatkov.
kazuje tabela 1. Algoritem smo ustavili, po 100000 klicih
ocenitvene funkcije. Zahvala
Kot je vidno iz tabele 3, nam je na skupini sekvenc D1 in Janez Brest in Borko Boˇskovi´c priznavata financiranje pri-
D2 uspelo polno poravnati 43 in 111 stolpcev. Programsko spevka s strani Javne agencije za raziskovalno dejavnost Re-
orodje Clustal Omega pa se je na istih sekvencah izkazalo publike Slovenije, raziskovalni program P2-0041 – Raˇcunal-
za boljˇse z 854 polno poravnanimi stolpci v skupini sekvenc niˇski sistemi, metodologije in inteligentne storitve.
LITERATURA
[1] PORAVNAVANJE ZAPOREDIJ.
http://web.bf.uni-lj.si/bi/biokemija/bioinfo/
2007/Material/Poravn1.htm, 2007. [Online; accessed
29-August-2017].
[2] B. Boˇskovi´c and J. Brest. Genetic Algorithm with
Advanced Mechanisms Applied to the Protein
StuCoSReC Proceedings of the 2017 4th Student Computer Science Research Conference 29
Ljubljana, Slovenia, 11 October
Parameter Vrednost
Velikost populacije 60
Dovoljeno ˇst. ovrednotenj 100000
Prostorsko razmerje 0,2
Horizontalno kriˇzanje 0,5
Vertikalno kriˇzanje 0,5
Tabela 2: Nabor podatkov [4].
Ime Sˇt. se- Povpreˇcna dolˇzina Identifikatorji
kvenc (Najkrajˇsa sekv., sekvenc
Najdaljˇsa sekv.)
D1 5 1092 (1006, 1142) M60059, M60060,
M60061, M60062,
M60063
Slika 4: Vertikalno kriˇzanje. D2 6 212 (211, 212) Z75841, Z75850,
Z75854, Z75852,
Z75858, Z75851
D1 in 206 v skupini sekvenc D2.
Tabela 3: Rezultati
Ime Sˇt. ujemajoˇcih Sˇt. ujemajoˇcih
stolpcev z EA stolpcev z Clustal
Omega
D1 43 854
D2 111 206
Slika 5: Horizontalno kriˇzanje. 4. ZAKLJUCˇ EK
Zaradi hitrosti smo algoritem implementirali v jeziku C++. V ˇclanku smo predstavili metodo poravnave sekvenc s po-
Eksperimente smo izvajali na osebnem raˇcunalniku z 16GB moˇcjo evolucijskega algoritma. Z naˇso implementacijo smo
spomina, 2.2GHz Intel Core i7 procesorjem in MacOS ope- uspeli doseˇci poravnavo sekvenc DNK. Algoritem bi lahko
racijskim sistemom. izboljˇsali v procesu mutacije, kjer bi z veˇc razliˇcnimi tipi
mutacij lahko dosegli veˇcjo raznolikost populacije. Potrebno
Uˇcinkovitost algoritma smo primerjali z uveljavljenim pro- bi bilo narediti tudi analizo vrednosti krmilnih parametrov.
gramskim orodjem Clustal Omega, ki spada v druˇzino pro- Npr. z veˇcjo populacijo in daljˇsim evolucijskim procesom bi
gramov Clustal (http://www.ebi.ac.uk/Tools/msa/clustalo/). verjetno dobili boljˇse rezultate. Implementacija bolj kom-
Uspeˇsnost poravnav obeh algoritmov smo ocenili s ˇstevilom pleksne ocenitvene funkcije in generacija zaˇcetne populacije,
polno ujemajoˇcih se stolpcev v poravnavi. Uporabili smo po- ki ni nakljuˇcno generirana, predstavljata tudi dve izboljˇsavi
doben nabor podatkov, kot je bil uporabljen v [4] (tabela 2). za pridobitev boljˇse konˇcne poravnave. Razvoj algoritma se
Sekvence omenjene v [4] smo prenesli iz spletne strani evrop- bo nadaljeval v magistrskem delu, kjer bomo poleg porav-
skega inˇstituta za bioinformatiko (http://www.ebi.ac.uk). nave sekvenc DNK implementirali ˇse zmoˇznost poravnave
proteinov s pomoˇcjo razliˇcnih ocenitvenih matrik. Algori-
V implementiranem programu smo sekvence podali v teks- tem bomo bolj podrobno primerjali z drugimi sorodnimi re-
tovnem formatu FASTA in nastavili parametre, kot jih pri- ˇsitvami na veˇcjem naboru podatkov.
kazuje tabela 1. Algoritem smo ustavili, po 100000 klicih
ocenitvene funkcije. Zahvala
Kot je vidno iz tabele 3, nam je na skupini sekvenc D1 in Janez Brest in Borko Boˇskovi´c priznavata financiranje pri-
D2 uspelo polno poravnati 43 in 111 stolpcev. Programsko spevka s strani Javne agencije za raziskovalno dejavnost Re-
orodje Clustal Omega pa se je na istih sekvencah izkazalo publike Slovenije, raziskovalni program P2-0041 – Raˇcunal-
za boljˇse z 854 polno poravnanimi stolpci v skupini sekvenc niˇski sistemi, metodologije in inteligentne storitve.
LITERATURA
[1] PORAVNAVANJE ZAPOREDIJ.
http://web.bf.uni-lj.si/bi/biokemija/bioinfo/
2007/Material/Poravn1.htm, 2007. [Online; accessed
29-August-2017].
[2] B. Boˇskovi´c and J. Brest. Genetic Algorithm with
Advanced Mechanisms Applied to the Protein
StuCoSReC Proceedings of the 2017 4th Student Computer Science Research Conference 29
Ljubljana, Slovenia, 11 October
