Bioinformatica

Algoritmi de programare dinamică pentru aliniere de secvenţe

Aliniere globală – Algoritmul Needleman-Wunsch

Fie două secvenţe x şi y. Se construieşte o matrice F care are coloanele etichetate cu caracterele din x şi liniile cu caracterele din y. Aceasta se completează din colţul stânga-sus spre colţul dreapta-jos, fiecare locaţie F(i, j) din matrice specificând scorul celei mai bune alinieri până la x_i şi y_j.

Algoritmul de completare a matricei:

F(0, 0) = 0
              /
              |  F(i-1, j-1) + s(x[i], y[j])  // potrivire
F(i, j) = max <  F(i-1, j) - d                // insertie
              |  F(i, j-1) - d                // stergere
              \

unde s(x_i, y_j) este scorul alinierii lui x_i cu y_j (obţinut, de exemplu, dintr-o matrice de substituţie), iar d este penalizarea pentru gap.

Evident, F(0, j) = -jd, F(i, 0) = -id.

Scorul celei mai bune alinieri se găseşte în celula din colţul dreapta-jos al matricei. Identificarea alinierii propriu-zise se face printr-un procedeu de traceback (se urmăreşte, pornind din colţul dreapta-jos, înapoi, drumul parcurs pentru a obţine acest scor, până la atingerea colţului din stânga-sus.

Aliniere locală – Algoritmul Smith-Waterman

Alinierea locală are ca scop găsirea celei mai bune alinieri între subsecvenţe din x şi y.

Algoritmul este asemănător celui de mai sus, cu următoarele diferenţe:

• În afară de potrivire, ştergere şi inserţie, o altă opţiune este începerea unei noi alinieri locale, cu scor iniţial 0;
• Alinierea locală se poate termina oriunde în matrice, scorul ei fiind cel mai mare scor dintr-o celulă a matricei; pentru identificarea alinierii, se face traceback din acea celulă până când se întâlneşte o celulă cu scor 0.

F(0, 0) = 0
              /
              |  0                            // incepe o noua aliniere
              |  F(i-1, j-1) + s(x[i], y[j])  // potrivire
F(i, j) = max <  F(i-1, j) - d                // insertie
              |  F(i, j-1) - d                // stergere
              \

Matrice de substituţie

BLOSUM50 (BLOcks SUbstitution Matrix)

   A  R  N  D  C  Q  E  G  H  I  L  K  M  F  P  S  T  W  Y  V  B  Z  X
A  5 -2 -1 -2 -1 -1 -1  0 -2 -1 -2 -1 -1 -3 -1  1  0 -3 -2  0 -2 -1 -1
R -2  7 -1 -2 -4  1  0 -3  0 -4 -3  3 -2 -3 -3 -1 -1 -3 -1 -3 -1  0 -1
N -1 -1  7  2 -2  0  0  0  1 -3 -4  0 -2 -4 -2  1  0 -4 -2 -3  4  0 -1
D -2 -2  2  8 -4  0  2 -1 -1 -4 -4 -1 -4 -5 -1  0 -1 -5 -3 -4  5  1 -1
C -1 -4 -2 -4 13 -3 -3 -3 -3 -2 -2 -3 -2 -2 -4 -1 -1 -5 -3 -1 -3 -3 -2
Q -1  1  0  0 -3  7  2 -2  1 -3 -2  2  0 -4 -1  0 -1 -1 -1 -3  0  4 -1
E -1  0  0  2 -3  2  6 -3  0 -4 -3  1 -2 -3 -1 -1 -1 -3 -2 -3  1  5 -1
G  0 -3  0 -1 -3 -2 -3  8 -2 -4 -4 -2 -3 -4 -2  0 -2 -3 -3 -4 -1 -2 -2
H -2  0  1 -1 -3  1  0 -2 10 -4 -3  0 -1 -1 -2 -1 -2 -3  2 -4  0  0 -1
I -1 -4 -3 -4 -2 -3 -4 -4 -4  5  2 -3  2  0 -3 -3 -1 -3 -1  4 -4 -3 -1
L -2 -3 -4 -4 -2 -2 -3 -4 -3  2  5 -3  3  1 -4 -3 -1 -2 -1  1 -4 -3 -1
K -1  3  0 -1 -3  2  1 -2  0 -3 -3  6 -2 -4 -1  0 -1 -3 -2 -3  0  1 -1
M -1 -2 -2 -4 -2  0 -2 -3 -1  2  3 -2  7  0 -3 -2 -1 -1  0  1 -3 -1 -1
F -3 -3 -4 -5 -2 -4 -3 -4 -1  0  1 -4  0  8 -4 -3 -2  1  4 -1 -4 -4 -2
P -1 -3 -2 -1 -4 -1 -1 -2 -2 -3 -4 -1 -3 -4 10 -1 -1 -4 -3 -3 -2 -1 -2
S  1 -1  1  0 -1  0 -1  0 -1 -3 -3  0 -2 -3 -1  5  2 -4 -2 -2  0  0 -1
T  0 -1  0 -1 -1 -1 -1 -2 -2 -1 -1 -1 -1 -2 -1  2  5 -3 -2  0  0 -1  0
W -3 -3 -4 -5 -5 -1 -3 -3 -3 -3 -2 -3 -1  1 -4 -4 -3 15  2 -3 -5 -2 -3
Y -2 -1 -2 -3 -3 -1 -2 -3  2 -1 -1 -2  0  4 -3 -2 -2  2  8 -1 -3 -2 -1
V  0 -3 -3 -4 -1 -3 -3 -4 -4  4  1 -3  1 -1 -3 -2  0 -3 -1  5 -4 -3 -1
B -2 -1  4  5 -3  0  1 -1  0 -4 -4  0 -3 -4 -2  0  0 -5 -3 -4  5  2 -1
Z -1  0  0  1 -3  4  5 -2  0 -3 -3  1 -1 -4 -1  0 -1 -2 -2 -3  2  5 -1
X -1 -1 -1 -1 -2 -1 -1 -2 -1 -1 -1 -1 -1 -2 -2 -1  0 -3 -1 -1 -1 -1 -1

PAM 250 (Percentage of Acceptable point Mutations per 10⁸ years)

Ala(A)   2  
Cys(C)  -2  12 
Asp(D)   0  -5   4 
Glu(E)   0  -5   3   4 
Phe(F)  -4  -4  -6  -5   9 
Gly(G)   1  -3   1   0  -5   5 
His(H)  -1  -3   1   1  -2  -2   6 
Ile(I)  -1  -2  -2  -2   1  -3  -2   5 
Lys(K)  -1  -5   0   0  -5  -2   0  -2   5 
Leu(L)  -2  -6  -4  -3   2  -4  -2   2  -3   6 
Met(M)  -1  -5  -3  -2   0  -3  -2   2   0   4   6 
Asn(N)   0  -4   2   1  -4   0   2  -2   1  -3  -2   2 
Pro(P)   1  -3  -1  -1  -5  -1   0  -2  -1  -3  -2  -1   6 
Gln(Q)   0  -5   2   2  -5  -1   3  -2   1  -2  -1   1   0   4
Arg(R)  -2  -4  -1  -1  -4  -3   2  -2   3  -3   0   0   0   1   6
Ser(S)   1   0   0   0  -3   1  -1  -1   0  -3  -2   1   1  -1   0   2 
Thr(T)   1  -2   0   0  -3   0  -1   0   0  -2  -1   0   0  -1  -1   1   3
Val(V)   0  -2  -2  -2  -1  -1  -2   4  -2   2   2  -2  -1  -2  -2  -1   0   4 
Trp(W)  -6  -8  -7  -7   0  -7  -3  -5  -3  -2  -4  -4  -6  -5   2  -2  -5  -6  17 
Tyr(Y)  -3   0  -4  -4   7  -5   0  -1  -4  -1  -2  -2  -5  -4  -4  -3  -3  -2   0  10
        Ala Cys Asp Glu Phe Gly His Ile Lys Leu Met Asn Pro Gln Arg Ser Thr Val Trp Tyr
        (A) (C) (D) (E) (F) (G) (H) (I) (K) (L) (M) (N) (P) (Q) (R) (S) (T) (V) (W) (Y)

DNA Identity Matrix (v1)

      A          T         G       C        

 A    1     

 T   -10000     1    

 G   -10000    -10000     1    

 C   -10000    -10000    -10000    1

DNA Identity Matrix (v2)

    A  T  G  C        
 A  1     
 T -1  1    
 G -1 -1  1    
 C -1 -1 -1  1

DNA Substitution Matrix - Genome Analysis

      A    T    G    C        
 A   91     
 T -114  100    
 G  -31 -125  100    
 C -123  -31 -114   91

GAP-uri liniare vs. GAP-uri afine

Penalităţi de gap:

• Liniar: gap(g) = -gd

  (g = dimensiunea gap-ului; d = penalizarea pentru gap de dimensiune 1)

• Afin: gap(g) = -d - (g-1)e

  (g = dimensiunea gap-ului; d = penalizarea pentru îceputul gap-ului; e = penalizarea pentru extinderea gap-ului)

Exerciţiu

Temă