Aliniamentul local optimal şi spaţiile

50

Calculul unui aliniament local optimal prin programare dinamica

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
V(i-1,j-1)
V(i-1,j)
V(i,j-1)


+
+
+

,
σ(S[i],T[j]),
σ(S[i],-),
σ(-,T[j]),

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