R3libermihaela243 [619915]

ALGORITMI GENETICI OPTIMALI
Simon Alina-Roxana
Cuvinte cheie : aliniere , algoritm de aliniere , calcul paralel, matrice de aliniere,
paralelizare.
Introducere
Bioinformatica este un domeniu al  stiint ei ^ n care biologia,  stiint a despre
calculatoare  si tehnologia informat iei se unesc ^ ntr-o singur a disciplin a.
Bioinformatica a ap arut ca disciplin a ^ nrudit a cu informatica medical a, dedicat a
stoc arii  si prelucr arii datelor din biologie.
Algoritmii genetici s-au dovedit a  extrem de ecient i pentru un larg domeniu de
probleme de optimizare  si c autare. S-a acumulat o mare experient a^ n acest domeniu,
o clas a de tehnici adaptive de c autare, ^ n care munca de pionerat a fost efectuat a
acum mai bine 40 de ani de c atre J. Holland  si student ii s ai.
Calculul paralel reprezint a ^ n prezent un domeniu larg de interes exist^ and o
activitate de cercetare intens a ^ n acest sens, motivat a de numero si factori. Mereu
a fost nevoie de o solut ie de rezolvare a problemelor cu calcule foarte mari, dar
tehnologiile avansate au luat^ n calcul folosirea calculului paralel^ n rezolvarea acestor
probleme t in^ and cont  si de calculatoarele paralele din ce ^ n ce mai puternice.
Interesul de a aplica calculul paralel ^ n aplicat ii precum cele ce privesc analiza,
simularea  si optimizarea la scar a larg a a sistemelor interconectate, a crescut tot
mai mult. Calculul paralel se poate aplica de asemenea ^ n rezolvarea sistemelor de
ecuat ii, programarea matematic a  si ^ n problemele de optimizare, toate av^ and ca  si
proprietate comun a posibilitatea de a  descompuse ^ n subtask-uri.
Practic, de mai bine de 10 ani, orice calculator cont ine elemente de paralelism.
Acestea sunt sucient de bine ascunse pentru a nu schimba felul de a g^ andii al
utilizatorului.
Scopul acestui articol este de a prezenta o metod a de paralelizare a unui algoritm
genetic.
Liber Mihaela

Algoritmi secvent iali pentru alinierea secvent elor
biologice
Not iunea de aliniere. Alinierea global a  si local a.
Denit ia 1
Alinierea secvent elor este o metod a de comparare a dou a (sau mai multe secvent e)
prin scrierea lor una sub alta cu scopul de a evalua similaritatea^ ntre aceste secvent e.
Vorbim de aliniere global a ^ n cazul ^ n care compar am dou a secvent e ^ n
totalitatea lor.
^In evolut ia structurilor biologice acestea au suferit numeroase modic ari, ^ ns a
au p astrat frecvent anumite port iuni cu modic ari minore, conserv^ and astfel
funct ionalitatea acestor molecule, ^ n timp ce alte port iuni din molecul a pot avea
evolut ii divergente. De aceea se dore ste destul de des detectarea domeniilor comune
din proteine  si aprecierea gradului de similaritate ^ ntre aceste port iuni. Aceast a
analiz a se nume ste aliniere local a  si de si se poate aplica  si pentru alinierea unor
sect iuni extinse de ADN ^ n cele mai ^ nt^ alnite cazuri se aplic a pentru detect ia
similarit at ii ^ ntre secvent e divergente, cu origine comun a, ^ n care anumite port iuni
se p astreaz a.
Algoritmul Needleman-Wunsch
Algoritmul Needleman-Wunsch este considerat primul  si cel mai cunoscut
algoritm de programare dinamic a pentru alinierea global a a doua secvent e biologice.
A fost dezvoltat de Saul B. Needleman  si Christian D. Wunsch  si publicat ^ n anul
1970.
Algoritmul este ^ nc a folosit pe o scar a larg a pentru alinierea global a optim a, ^ n
particular ^ n cazul ^ n care calitatea alinierii este de o important  a major a.
^In bioinformatic a este folosit pentru alinierea secvent elor de proteine sau
nucleotide, ^ ns a poate  aplicat pentru orice fel de secvent e. Cu toate acestea,
algoritmul este considerat costisitor din punct de vedere al timpului  si spat iului
2

necesar, de aceea dezvolt arile recente ale algoritmului sau concentrat pe eliminarea
acestor dezavantaje, ment in^ and ^ n acela si timp calitatea acestuia.
Clasicarea sistemelor de calcul paralel
Un sistem de calcul paralel este un calculator cu mai multe procesoare care
lucreaz a ^ n paralel. Noile procesoare de tip multimiez pentru PC-uri sunt de
asemenea sisteme de calcul paralel.
Exist a multe tipuri de sisteme de calcul paralel, acestea deosebindu-se ^ n primul
r^ and prin tipul de interconectare:
^Intre procesoarele componente.
^Intre procesoare  si memorie.
De mai mult de 40 de ani, aproape toate calculatoarele au urmat un model comun
de ma sin a cunoscut sub numele matematicianului John von Neumann. Un calculator
von Neumann utilizeaz a conceptul de program memorat. Unitatea central a execut a
un program depus ^ n memorie care indica secvent a de operat ii, de citiri  si de scrieri
^ n/din memorie.
Paralelizarea algoritmilor de aliniere a secvent elor
biologice
Paralelizarea algoritmului Needleman-Wunsch
Majoritatea ^ ncerc arilor de a accelera algortimul Needleman-Wunsch s-au
concentrat pe calculul matricei de aliniere.
^In continuare va  analizat a o metod a paralel a care are ca punct de plecare o
alternativ a nerecursiv a pentru algoritmul trace-back. Aceast a alternativ a se bazeaz a
pe propriet at ile de simetrie care apar la compararea matricei Fcu matricea F,
matricea de programare dinamic a a secvent elor S
1 siS
2, undeS
1 siS
2reprezint a
secvent eleS1 siS2^ n ordine invers a.
3

Propriet at ile matricei de programare dinamic a
Hirschberg a introdus un algoritm de spat iu O(m+n) pentru g asirea celui mai
lung sub sir comun al unei perechi de  siruri de caractere. Metoda se bazeaz a pe
faptul c a cel mai lung sub sir comun al secvent elor S1 siS2este acela si cu cel al
secvent elor S
1 siS
2.
^In continuare vor  dezvoltate fundamentele matematice ale algoritmului
Hirschberg-ANW (Algoritmul Needleman-Wunsch), ^ ntr-un mod potrivit
paraleliz arii algoritmului Needleman-Wunsch.
SimetriaFF
Lema 1
Alinierea optim a a unei perechi ( S1;S2) ^ n ordine invers a este o
aliniere optim a pentru perechea ( S
1;S
2)  si invers.
Urm atoarea teorem a este esent ial a pentru metoda de paralelizare  si economisire
a spat iului a algoritmului Needleman-Wunsch.
Teorema 1
FieF siFmatricele de scoruri obt inute cu algoritmul Needleman-Wunsch pentru
perechile: (S1;S2)  si (S
1;S
2). Atunci pentru ecare k  si j, unde
0km  si 0jn, avem:
i.F[k;j] +F[mk;nj]F[m;n]
ii.F[k;j] +F[mk;nj] =F[m;n] dac a  si numai dac a [k,j] este o cale a
algoritmului trace-back.
Demonstrat ie. Armat ia i se demonstreaz a prin induct ie dup a k sij. Astfel
relat ia devine F[0;0] +F[m; n ]. Aceast a relat ie este adev arat a deoarece aplic^ and
Lema 3.1.1 se obt ine: F[m;n] =F[m;n]  siF[0;0] = 0. Se presupune c a exist a o
pereche de indici k, j pentru care F[k;j] +F[mk;nj]F[m;n]  si se vor
demonstra ^ n aceast a ipotez a relat iile:
(a)F[k+ 1;j] +F[mk1;nj]F[m;n],
4

(b)F[k;j+ 1] +F[mk;nj1]F[m;n],
(c)F[k+ 1;j+ 1] +F[mk1;nj1]F[m;n], sunt adev arate.
Relat ia (a) este adev arat a deoarece din denit ia recursiunii
F[k+ 1;j]F[k;j] +
avem:
F[k+ 1;j] +F[mk1;nj]F[k;j] +
+F[mk1;nj]
F[k;j] +F[mk;nj]F[m;n].
Relat ia (b) se demonstreaz a similar, iar pentru a demonstra relat ia ( c)B[k;j] se
consider a intrarea perechii ( xk;yj) ^ n matricea de substitut ie. Atunci,
F[k+ 1;j+ 1] +F[mk1;nj1]
F[k;j] +B[k+ 1;j+ 1] +F[mk1;nj1]
F[k;j] +F[mk;nj]F[m;n].
Armat ia ii este o consecint  a direct a din Lema 1.
Relat ia index ([ k;j];[mk;nj]) este denumit a simetrie FFiar intr arile
F[k;j]  siF[mk;nj] sunt denumite intr ari simetrice FF.
Spat iulO(m+n)Hirschberg-ANW
Teorema 1 ofer a bazele matematice pentru economisirea spat iului Hirschberg-
ANW. Prin metoda divide  si cucere ste, folosind de ecare dat a prima parte a
algoritmului Needleman-Wunsch peste secvent e de aproximativ jum atate din
dimensiunea precedent a, astfel ^ mp art ind problema ^ n subprobleme. Acest a metod a,
numit a faz a de divizare, se repet a pe ecare subsecvent  a nou a p^ an a c^ and se ajunge
la o lungime predeterminat a a subsecvent ei  si se ^ ncheie prin aplicarea algoritmului
Needleman-Wunsch la ecare dintre subsecvent ele obt inute. Faza de divizare poate
efectuat a ^ n timp O(mn), dar cu o constant a mai mare. Costul ^ n spat iul de memorie
este redus ^ n cel mai bun caz la O(m+n). A doua faz a, numit a faz a de cucerire, este
liniar a ^ n timp  si spat iu, deoarece const a ^ n unirea segmentelor calculate la sf^ ar situl
fazei de divizare.
Studiu de caz
Pentru a ilustra tehnica divide  si cucere ste a spatiului Hirschberg-ANW se
consider a dou a secvent e S1=HEAGAWGHEE  siS2=PAWHEAE  si se pune
problema g asirii unei alinieri optime a celor dou a secvent e.
5

^In prima etap a a fazei de divizare se consider a j=5  si se ^ mparte secvent a S1
^ n dou a jumat at i, ambele av^ and dimensiunea 5. A doua jum atate se va scrie ^ n
ordine invers a. Astfel, problema init ial a, cea de a alinia secvent ele S1 siS2, ^ n dou a
probleme independente:
1.Alinierea secvent elor: HEAGA  siPAWHEAE ;
2.Alinierea secvent elor: EEHGW  siEAEHWAP ;
^Inainte de a calcula matricile de programare dinamic a, este important de
remarcat faptul c a modul de calcul al acestora prin algoritmul Needleman-Wunsch
poate  schimbat prin calculul coloanei din dreapta a matricei, utiliz^ and doar spat iul
de stocare al unei coloane.
Acest calcul este reprezentat prin urm atorul pseudo-cod care utilizeaz a o matrice
unidimensional a C[k], unde 0km, pentru a stoca rezultatele intermediare  si
nale.
For k = 1to m
Aux2 C[k]
If Aux 2 +
> Aux 1 +r(xk; character )
C[k] Aux2 +

Else
C[k] Aux1 +r(xk; character )
If C [k]< C[k1] +

C[k] C[k1] +

If C [k]<0
C[k] 0
Aux1 Aux2
Return C
6

Figura 1: Matricea F
Figura 2: Matricea F
Prin ad augarea intr arilor simetrice FFa coloanelor din dreapta matricelor
de programare dinamic a se constat a c a:
2 =arg maxfF[k;5] +F[7k;5] : 0k7g.
Prin urmare [2 ;5] este o cale a algoritmului trace-back, iar c autarea
segmentului c aii din st^ anga lui [2 ;5] este redus a la mult imea indicilor
f[r;s] : 0r2;0s5g, ^ n timp ce c autarea segmentului din dreapta lui
[2;5] este redus a la f[r;s] : 2r7;5s10g, sau ^ n termenii lui Fla
f[r;s] : 0r5;0s5g.
Urm atorul pas este de a diviza secvent ele astfel obt in^ andu-se perechile
7

(HEAGA;PA )  si (EEHGW;EAEHW ).
^In acest moment algoritmul veric a dac a lungimile tuturor segmentelor de
secvent  a din urm a sunt mai mici sau egale cu lungimea maxim a stabilit a.
Dac a nu se ^ nt^ ampl a acest lucru, subsecvent ele HEAGA  siEEHGW sunt
^ mp art ite ^ n dou a secvent e noi, iar procesul de mai sus este repetat pentru a obt ine
dou a perechi reduse pentru ecare. Aceast a descompunere genereaz a un arbore
binar care la ecare frunz a are o pereche de segmente ale subsecvent elor init iale a
c aror lungime este mai mic a sau egal a cu lungimea maxim a stabilit a.
^In acest moment se determin a o cale a algoritmului trace-back pentru ecare
pereche  si ^ ncepe faza de cucerire. Se presupune c a lungimea maxim a stabilit a este
5, apoi se calculeaz a urm atoarele matrici de programare dinamic a.
Aplic^ and algoritmul trace-back al algoritmului Needleman-Wunsch pentru ecare
dintre cele dou a matrici se obt in c aile f[2;5];[1;4];[1;3];[0;2];[0;1];[0;0]grespectiv
8

f[5;5];[4;4];[4;3];[3;2];[2;1];[1;1];[0;0]g.
Aplic^ andu-se regulile pentru alinierea secvent elor discutate anterior se obt in ali-
nierile urm atoare:
Paralelizarea Hirschberg-ANW
Paralelizarea metodei discutate anterior exploateaz a toate calculele independente
diviz^ and  si cucerind faze. Acestea sunt calculul coloanei din dreapta a matricei
de programare dinamic a pentru alinierea optim a a ec arei perechi de subsecvent e,
calculul c ailor algoritmului trace-back pentru ecare pereche de subsecvent e cu o
lungime mai mic a sau egal a cu lungimea stabilit a  si producerea alinierilor
corespunz atoare.
Se utilizeaz a pentru descrierea metodei paralele modelul maestru-muncitor cu
un num ar de 2pmuncitori. Fiecare muncitor este identicat printr-un num ar de
identicare q, unde 1q2p. Num arul de identicare al maestrului este 0.
Implementarea algoritmului impune o condit ie suplimentar a pentru oprirea
fazei de divizare. Aceasta oprindu-se atunci c^ and lungimea tuturor subsecvent elor
este mai mic a sau egal a dec^ at lungimea stabilit a L>0 sau c^ and tot i muncitorii sunt
ocupat i.
Dac a sunt ^ ndeplinite condit iile pentru divizarea unei subsecvent e la muncitorul
q, atunci muncitorul qp astreaz a prima jum atate a segmentului S1 si primelek
caractere din segmentul S2pentru a repeta procesele asupra lor  si pentru a trimite
a doua jum atate din S1 si caracterele, ^ n num ar de mk, r amase din S2^ n ordine
9

invers a la muncitorul q+ 2p1. Astfel dac a de exemplu p= 2  si condit iile pentru
divizarea secvent elor sunt ^ ntotdeauna ^ ndeplinite, faza de divizare va implica doi
pa si paraleli.
^In primul r^ and maestrul trimite sarcini la muncitorul 1  si la muncitorul 2. C^ and
aceste activit at i paralele sunt terminate, munciorul 1 trimite o sub-sarcin a
muncitorului 3  si muncitorul 2 trimite o sub-sarcin a muncitorului 4. Tot i cei
patru muncitori ^  si proceseaz a sarcinile ^ n paralel. Astfel sarcinile paralele ^ n faza
de divizare creeaz a un arbore binar de ^ n alt ime 2, sarcina maestrului reprezent^ and
r ad acina.
Faza de cucerire traverseaz a acest arbore de la frunze ^ n sus ^ ntr-un num ar de p
pa si suplimentari paraleli. ^In primul r^ and, muncitorii 1,2,3  si 4 produc alinierea lor
local a ^ n paralel. Apoi muncitorul 1 trimite alinierea muncitorului 2, iar muncitorul
3 trimite alinierea muncitorului 4. ^In acest moment muncitorul 2  si muncitorul 4
concateneaz a alinierile lor ^ n paralel  si trimit rezultatul maestrului.
Pipelining
Dup a revenirea la alinierea lor local a, muncitorul 1  si muncitorul 2 sunt inactivi.
Prin urmare o nou a pereche de secvent e ( S1;S2) poate  primit a de la maestru.
Retururile ulterioare de la lucr atori elibereaz a procesoarele necesare pentru ca
secvent ele noi s a creeze arborele binar, dac a este necesar.
Acest lucru este potrivit ^ n special pentru procesarea paralel a a unei secvent e de
interogare.
Concluzie
^In concluzie metoda paralel a are teoretic o vitez a superioar a fat  a de algoritmul
Needleman-Wunsch  si permite procesarea prin pipeline a unei secvent e de interogare
fat a de o baz a de date cu secvent e.
10

Bibliograe
[1] Bogdan Dumitrescu, Algoritmi de calcul paralel , 2001
[2] Gheorghe Ioan-Mihala s, Anca Tudor, Sorin Paralescu, Bioinformatica , Editura
Victor Babe s, Timi soara, 2011
[3] Gheorghe M. Panaitescu, Arhitecturi paralele de calcul , Universitatea Petrol-
Gaze Ploie sti, Catedra Automatic a  si Calculatoare, 2009
[4] Ioana Chiorean, Calcul paralel: Fundamente , Editura Albastr a, 1999
[5] Jaime Seguel, Carlos Torres, Paralellization of Needleman-Wunsch String
Alignment Method , 2011
[6] Octavian Paiu, Vladimir Dumitrescu, Algoritmi genetici seriali  si paraleli ,
Revista Informatica Economic a, 1998
11