Calculul unui aliniament optim prin programare dinamică

45

    Fiind date şirurile S şi T, cu |S|=n şi |T|=m, scopul nostru este de a calcula aliniamentul optim al lui S cu T. pentru a atinge acest scop, definim V(i,j) ca valoarea aliniamentului optim al şirurilor S[1]...S[i] şi T[1]...T[j].

Valoarea unui aliniament optimal al lui S şi T este atunci V(n,m). Elementul crucial al programării dinamice este de a rezolva problema mai generală de a calcula toate valorile V(i,j) cu 0≤i<n şi 0≤j<m, īn ordinea crescătoare a lui i şi j. Fiecare dintre acestea vor fi relativ simplu de calculat, avānd date valorile deja calculate pentru valori mai mici ale i şi/sau j, folosind o relaţie de recurenţă. Pentru a porni procesul, avem nevoie de valorile iniţiale de la care porneşte recurenţa, aici i=0 şi sau j=0.

Valorile iniţiale se calculează prin:

V(i,0)=

i
Σ
 k=1

 σ(S[k],-)

V(0,j)=

i
Σ
 k=1

 σ(-,T[k])

    Valorile iniţiale V(i,0) definite astfel īnseamnă că i caractere ale lui S vor fi aliniate cu 0 caractere ale lui T, ceea ce este echivalent cu a spune că ele vor fi aliniate cu spaţii. Semnificaţia lui V(0,j) este analogă.

Relaţia de recurenţă este:

V(i,j)=max

V(i-1,j-1)
V(i-1,j)
V(i,j-1)

+
+
+

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

    Această formulă poate fi īnţeleasă considerānd un aliniament optimal a primelor i caractere din S cu primele j caractere din T. Īn particular, să considerăm ultima pereche de caractere dintr-un astfel de aliniament. Această ultimă pereche trebuie să fie una dintre următoarele (Īn esenţă, ce aduagă ultimele litere introduse: 1) o aliniere a ultimelor doua caractere, 2) ultimul caracter introdus din S este aliniat cu spaţiu, sau 3) ultimul caracter introdus din T este aliniat cu un spatiu);

1. (S[i],T[j]), caz īn care aliniamentul din stānga unei astfel de perechi trebuie să fie un aliniament optimal al S[1]...S[i-1] şi T[1]...T[j-1], adică trebuie să aibă valoarea V(i-1,j-1), sau

2. (S[i],-), caz īn care aliniamentul din stānga trebuie să aibe valoarea V(i-1,j), sau

3. (-,T[j]), caz īn care aliniamentul din stānga trebuie să aibe valoarea V(i,j-1).

Aliniamentul optim alege pe aceea dintre aceste trei posibilităţi cu cea mai mare valoare.

© Cornel Mironel Niculae, 2003-2008

13-Nov-2009