Page 27 - 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. 27
lucijski algoritem za poravnavo sekvenc
Adel Burekovic´ Janez Brest Borko Boškovic´
Univerza v Mariboru Univerza v Mariboru Univerza v Mariboru
Fakulteta za elektrotehniko, Fakulteta za elektrotehniko, Fakulteta za elektrotehniko,
racˇunalništvo in informatiko racˇunalništvo in informatiko racˇunalništvo in informatiko
Koroška cesta 46 Koroška cesta 46 Koroška cesta 46
2000 Maribor 2000 Maribor 2000 Maribor
burekovic.adel@gmail.com janez.brest@um.si borko.boskovic@um.si
POVZETEK Slika 1: Primer poravnave sekvenc z vnosom vrzeli.
V ˇclanku predstavimo reˇsevanje problema poravnave biolo- V literaturi zasledimo, da so se pri poravnavi dveh sekvenc
ˇskih sekvenc s pomoˇcjo evolucijskega algoritma. Kandidate izkazali za zelo uspeˇsne algoritmi, ki uporabljajo metode
v populaciji smo evaluirali z metodo sume parov. Ker je pro- dinamiˇcnega programiranja. Zˇe leta 1970 sta Needleman
blem lahko ˇcasovno zahteven, smo algoritem implementirali in Wunsch predlagala metodo za poravnavo dveh sekvenc
s pomoˇcjo jezika C++. Uspeˇsnost algoritma smo testirali na [9]. Dinamiˇcno programiranje se ne uporablja za primerjavo
DNK sekvencah razliˇcnih dolˇzin. Na skupini sekvenc pov- veˇcjega ˇstevila sekvenc zaradi raˇcunske zahtevnosti O(nk),
preˇcne dolˇzine 212 simbolov smo poravnali 111 stolpcev se- kjer k predstavlja ˇstevilo sekvenc [7]. Zaradi velike raˇcunske
kvenc. Pri sekvencah povpreˇcne dolˇzine 1092 simbolov smo zahtevnosti se pri primerjavi veˇcjega ˇstevila sekvenc upora-
pa dosegli slabˇse rezultate z samo 43 poravnanimi stolpci. bljajo metode, ki ne zagotavljajo najboljˇse poravnave [8].
Med takˇsne spadajo progresivne metode [5], ki so med dru-
Kjucˇne besede gimi implementirane tudi v Clustal Omega [12] in T-Coffee
[10]. Drugi moˇzen pristop so iterativne metode, ki poskuˇsajo
poravnava sekvenc, evolucijski algoritem, kriˇzanje, mutacija, skozi iteracije izboljˇsati zaˇcetno reˇsitev tako, da maksimizi-
optimizacija rajo dano ocenitveno funkcijo [8]. Med iterativne pristope
spada tudi naˇsa implementacija z evolucijskim algoritmom
1. UVOD [8].
Poravnava sekvenc je metoda, pri kateri je cilj najti podob- V drugem poglavju opiˇsemo implementiran algoritem za po-
nosti med naborom dveh (angl. pair-wise alignment) ali veˇc ravnavo sekvenc s pomoˇcjo evolucijskega algoritma. V tre-
(angl. multiple sequence alignment) sekvenc simbolov [8]. tjem poglavju predstavimo program in eksperimente, kjer
V bioinformatiki se sekvence DNK, RNK in proteinov po- testiramo uspeˇsnost algoritma na razliˇcnih sekvencah DNK.
ravnavajo z namenom iskanja skupnih znaˇcilnosti, ki bi na- Zadnje poglavje je namenjeno razpravi.
kazovale evolucijsko povezavo [8]. Teˇzave pri poravnavah
se pojavijo zaradi tega, ker se s procesom evolucije skozi 2. EVOLUCIJSKI ALGORITEM
ˇcas v sekvencah pojavijo mutacije, kot so vnosi, brisanje in
substitucija genetskih informacij, kar povzroˇci razlike med Evolucijski algoritmi so metode, ki poskuˇsajo z oponaˇsa-
sekvencami [7]. njem naravnih procesov kriˇzanja, mutacije in selekcije iz-
boljˇsati populacijo kandidatov. Primerni so za reˇsevanje
Sekvence so predstavljene po vrsticah, v katerih poskuˇsamo razliˇcnih kombinatoriˇcnih problemov kot sta npr. optimi-
simbole preurediti na takˇsen naˇcin, da bo konˇcni rezultat zacija zvijanja proteinov [2] in poravnava sekvenc. V na-
matrika, ki ima po stolpcih ˇcim veˇc enakih ali podobnih ˇsem algoritmu so sekvence v kandidatih predstavljene v dvo-
simbolov [8]. Po potrebi se v sekvence vnesejo tudi vrzeli dimenzionalnem polju po vrsticah. V algoritmu je vsak kan-
(angl. gaps) z namenom pridobitve ˇcim bolj optimalne po- didat v populaciji generiran nakljuˇcno glede na vhodne se-
ravnave [1]. V primeru sekvenc DNK so baze adenin, citozin, kvence in predstavlja potencialno reˇsitev. Implementacijo
gvanin in timin v sekvenci predstavljene s simboli A, C, G in algoritma prikazuje slika 2.
T. Primer poravnave treh manjˇsih sekvenc DNK z vnosom
vrzeli prikazuje slika 1. Najbolj optimalna poravnava je bila Kvaliteto kandidatov smo ocenili z metodo vsote parov (angl.
doseˇzena z poveˇcanjem maksimalne dolˇzine sekvenc in vsta- sum of pairs) [11], pri kateri smo vsak stolpec ovrednotili po
vljanjem vrzeli. naslednji enaˇcbi:
StuCoSReC Proceedings of the 2017 4th Student Computer Science Research Conference DOI: https://doi.org/10.26493/978-961-7023-40-4.27-30 27
Ljubljana, Slovenia, 11 October
Adel Burekovic´ Janez Brest Borko Boškovic´
Univerza v Mariboru Univerza v Mariboru Univerza v Mariboru
Fakulteta za elektrotehniko, Fakulteta za elektrotehniko, Fakulteta za elektrotehniko,
racˇunalništvo in informatiko racˇunalništvo in informatiko racˇunalništvo in informatiko
Koroška cesta 46 Koroška cesta 46 Koroška cesta 46
2000 Maribor 2000 Maribor 2000 Maribor
burekovic.adel@gmail.com janez.brest@um.si borko.boskovic@um.si
POVZETEK Slika 1: Primer poravnave sekvenc z vnosom vrzeli.
V ˇclanku predstavimo reˇsevanje problema poravnave biolo- V literaturi zasledimo, da so se pri poravnavi dveh sekvenc
ˇskih sekvenc s pomoˇcjo evolucijskega algoritma. Kandidate izkazali za zelo uspeˇsne algoritmi, ki uporabljajo metode
v populaciji smo evaluirali z metodo sume parov. Ker je pro- dinamiˇcnega programiranja. Zˇe leta 1970 sta Needleman
blem lahko ˇcasovno zahteven, smo algoritem implementirali in Wunsch predlagala metodo za poravnavo dveh sekvenc
s pomoˇcjo jezika C++. Uspeˇsnost algoritma smo testirali na [9]. Dinamiˇcno programiranje se ne uporablja za primerjavo
DNK sekvencah razliˇcnih dolˇzin. Na skupini sekvenc pov- veˇcjega ˇstevila sekvenc zaradi raˇcunske zahtevnosti O(nk),
preˇcne dolˇzine 212 simbolov smo poravnali 111 stolpcev se- kjer k predstavlja ˇstevilo sekvenc [7]. Zaradi velike raˇcunske
kvenc. Pri sekvencah povpreˇcne dolˇzine 1092 simbolov smo zahtevnosti se pri primerjavi veˇcjega ˇstevila sekvenc upora-
pa dosegli slabˇse rezultate z samo 43 poravnanimi stolpci. bljajo metode, ki ne zagotavljajo najboljˇse poravnave [8].
Med takˇsne spadajo progresivne metode [5], ki so med dru-
Kjucˇne besede gimi implementirane tudi v Clustal Omega [12] in T-Coffee
[10]. Drugi moˇzen pristop so iterativne metode, ki poskuˇsajo
poravnava sekvenc, evolucijski algoritem, kriˇzanje, mutacija, skozi iteracije izboljˇsati zaˇcetno reˇsitev tako, da maksimizi-
optimizacija rajo dano ocenitveno funkcijo [8]. Med iterativne pristope
spada tudi naˇsa implementacija z evolucijskim algoritmom
1. UVOD [8].
Poravnava sekvenc je metoda, pri kateri je cilj najti podob- V drugem poglavju opiˇsemo implementiran algoritem za po-
nosti med naborom dveh (angl. pair-wise alignment) ali veˇc ravnavo sekvenc s pomoˇcjo evolucijskega algoritma. V tre-
(angl. multiple sequence alignment) sekvenc simbolov [8]. tjem poglavju predstavimo program in eksperimente, kjer
V bioinformatiki se sekvence DNK, RNK in proteinov po- testiramo uspeˇsnost algoritma na razliˇcnih sekvencah DNK.
ravnavajo z namenom iskanja skupnih znaˇcilnosti, ki bi na- Zadnje poglavje je namenjeno razpravi.
kazovale evolucijsko povezavo [8]. Teˇzave pri poravnavah
se pojavijo zaradi tega, ker se s procesom evolucije skozi 2. EVOLUCIJSKI ALGORITEM
ˇcas v sekvencah pojavijo mutacije, kot so vnosi, brisanje in
substitucija genetskih informacij, kar povzroˇci razlike med Evolucijski algoritmi so metode, ki poskuˇsajo z oponaˇsa-
sekvencami [7]. njem naravnih procesov kriˇzanja, mutacije in selekcije iz-
boljˇsati populacijo kandidatov. Primerni so za reˇsevanje
Sekvence so predstavljene po vrsticah, v katerih poskuˇsamo razliˇcnih kombinatoriˇcnih problemov kot sta npr. optimi-
simbole preurediti na takˇsen naˇcin, da bo konˇcni rezultat zacija zvijanja proteinov [2] in poravnava sekvenc. V na-
matrika, ki ima po stolpcih ˇcim veˇc enakih ali podobnih ˇsem algoritmu so sekvence v kandidatih predstavljene v dvo-
simbolov [8]. Po potrebi se v sekvence vnesejo tudi vrzeli dimenzionalnem polju po vrsticah. V algoritmu je vsak kan-
(angl. gaps) z namenom pridobitve ˇcim bolj optimalne po- didat v populaciji generiran nakljuˇcno glede na vhodne se-
ravnave [1]. V primeru sekvenc DNK so baze adenin, citozin, kvence in predstavlja potencialno reˇsitev. Implementacijo
gvanin in timin v sekvenci predstavljene s simboli A, C, G in algoritma prikazuje slika 2.
T. Primer poravnave treh manjˇsih sekvenc DNK z vnosom
vrzeli prikazuje slika 1. Najbolj optimalna poravnava je bila Kvaliteto kandidatov smo ocenili z metodo vsote parov (angl.
doseˇzena z poveˇcanjem maksimalne dolˇzine sekvenc in vsta- sum of pairs) [11], pri kateri smo vsak stolpec ovrednotili po
vljanjem vrzeli. naslednji enaˇcbi:
StuCoSReC Proceedings of the 2017 4th Student Computer Science Research Conference DOI: https://doi.org/10.26493/978-961-7023-40-4.27-30 27
Ljubljana, Slovenia, 11 October
