50
|
|
|
|
50 |
Definiţia 3.1: Şirul e este vid dacă |e|=0.
Definiţia 3.2: U este prefix al lui S dacă şi numai dacă U=S[1] S[k] sau U=e, unde 1≤ k≤ n.
Definiţia 3.3: U este sufix al lui S dacă şi numai dacă U=S[k] S[n] sau U=e, unde 1≤ k≤ n.
De exemplu, fie S=abcxdex. Mulţimea prefixelor lui S conţine pe ab, iar mulţimea sufixelor pe xdex. Şirul vid e este atāt prefix cāt şi sufix al lui S.
Definiţia 3.4: Fie S şi T două şiruri cu |S|=n şi |T|=m. Pentru 1 ≤ i ≤ n şi 1 ≤ j ≤ m, fie n(i,j) valoarea maximă a unui aliniament optimal (global) ale sufixelor a şi b dintre toate sufixele a ale S[1] S[i] şi toate sufixele b ale T[1] T[j].
De exemplu, să presupunem S=abcxdex şi T=xxxcde. Să punctăm, ca şi pānǎ acum, o potrivire cu +2 şi o nepotrivire sau spaţiu cu -1. Atunci n(5,5)=3, cu a=cxd şi b=cd, şi aliniamentul
|
c |
x |
d |
|
c |
- |
d |
|
+2 |
-1 |
+2 |
Algoritmul de programare dinamică pentru aliniamentul local optimal este similar cu algoritmul de programare dinamică pentru aliniamentul optimal global dat īn Secţiunea alocata calculului alinierii optimale globale. El umple un tabel cu valorile lui n(i,j), cu i şi j crescătoare. Valoarea fiecărei casete este calculată conform cu nişte noi condiţii iniţiale şi relaţie de recurenţă pentru n(i,j) care vor fi date īn continuare. Spre deosebire de algoritmul alinierii globale, valoarea aliniamentului local optimal poate fi găsit īn orice casetă, care conţine maximul tuturor celor (n+1)(m+1) valori ale n(i,j). Aceasta deoarece fiecare n(i,j) reprezintă o pereche optimă (a,b) de sufixe a unei perechi date (i,j) de prefixe. Īntrucāt un sufix al unui prefix este doar un subşir, găsim pereche optimă de subşiruri maximizānd n(i,j) pentru toate posibilele perechi de prefixe (i,j).
Condiţiile iniţiale: Pentru simplitate, vom face presupunerea rezonabilă că s(x,-)£0 şi s(-,x)£0. Atunci
n(i,0)=0, şi
n(0,j)=0,
deoarece sufixul optimal de a alinia cu un şir de lungime 0 este sufixul vid.
Relaţia de recurenţă: Pentru i > 0 şi j > 0,
|
V(i,j)=max |
 |
0 |
|
, |
 |
Formula arată foarte asemănător cu formula de recurenţă pentru aliniamentul global optimal din secţiunea precedentă. Desigur semnificaţia este oarecum diferită şi avem un termen suplimentar īn funcţia max.
Recurenţa este explicată īn cele ce urmează. Să considerăm un aliniament A al unui sufix a al S[1] S[i] şi un sufix b al T[1] T[j]. Există patru cazuri posibile:
1.
a = e şi b = e, caz īn care aliniamentul are valoarea 0.2.
a ¹ e şi b ¹ e, şi ultima pereche aliniată īn A este (S[i],T[j]), caz īn care restul lui A are valoarea n(i-1,j-1).3.
a ¹ e şi ultima pereche aliniată īn A este (S[i],-), caz īn care restul lui A are valoarea n(i-1,j).4.
b ¹ e şi ultima pereche aliniată īn A este (-,T[j]), caz īn care restul lui A are valoarea n(i,j-1).Dintre aceste aliniamentul optimal alege cazul care are cea mai mare valoare.
© Cornel Mironel Niculae, 2003-2008
13-Nov-2009