SEDE BOGOTA DNSAV

cap. 2 alineamiento

ALINEAMIENTO GLOBAL DE UN PAR DE SECUENCIAS POR MEDIO DEL ALGORITMO DE NEEDLEMAN & WUNSCH

Este algoritmo encuentra el alineamiento global de dos secuencias via Programación Dinámica.

Procedimiento:

Dadas dos secuencias A y B.

A=a₁a₂...a_ny B=b₁b₂...b_m

Se define:

Una función de similitud (coincidencias) S(a_i,b_j) entre los elementos a_i y b_j de las secuencias a alinear.
Los in/dels (inserciones o deleciones) se penalizan con un peso W.
Se construye una matriz H de i+1 filas y j+1 columnas. (La secuencia A se ubica en las filas y la secuencia B en las columnas

Inicialización: Se inicializa con ceros la primera fila y la primera columna del ma matriz H.
Llenado de Matriz (scoring): La posición H_ij es la máxima similitud de dos segmentos que terminan en ai y bj respectivamente. El valor de H_ij depende únicamente del los valores H(i-1,j-1) , H(i-1, j) y H(i, j-1) como se ilustra en la figura 1.

Figura 1. Cálculo del valor en la posición H_ij.
Recuperación de la solución (Backtracking): Consiste en tomar la última coincidencia del alineamiento y comenzar a buscar el camino que maximice la función. El retroceso comienza en la posición i+1,j+1 de la matriz, es en ésta posición donde se presenta el máximo puntaje del alineamiento.
El algoritmo recorre los vecinos de la celda actual para identificar sus predecesores, es decir observa el vecino a la izquierda , el vecino en la diagonal y el vecino de arriba, y se selecciona el vecino que presente el valor más alto. Es de notar que en el caso que se presente un empate en posible obtener diferentes alineamientos para las mismas secuencias.

Ejemplo:

Alinear las siguientes secuencias:
A = GAATTCAGTTA
B = GGATCGA

Parámetros:
Coincidencias = 1
No coincidencias = 0
Huecos = 0

Inicialización:(Tabla 1)

			1	2	3	4	5	6	7
			G	G	A	T	C	G	A
		0	0	0	0	0	0	0	0
1	G	0
2	A	0
3	A	0
4	T	0
5	T	0
6	C	0
7	A	0
8	G	0
9	T	0
10	T	0
11	A	0

Tabla 1. Inicialización.

Llenado de la Matriz: (Tabla 2)

			1	2	3	4	5	6	7
			G	G	A	T	C	G	A
		0	0	0	0	0	0	0	0
1	G	0	1	1	1	1	1	1	1
2	A	0	1	1	2	2	2	2	2
3	A	0	1	1	2	2	2	2	3
4	T	0	1	1	2	3	3	3	3
5	T	0	1	1	2	3	3	3	3
6	C	0	1	1	2	3	4	4	4
7	A	0	1	1	2	3	4	4	5
8	G	0	1	2	2	3	4	5	5
9	T	0	1	2	2	3	4	5	5
10	T	0	1	2	2	3	4	5	5
11	A	0	1	2	3	3	4	5	6

Tabla 2. Llenado de la matriz.

Recuperación de la solución (Backtracking):

			1	2	3	4	5	6	7
			G	G	A	T	C	G	A
		0	0	0	0	0	0	0	0
1	G	0	1	1	1	1	1	1	1
2	A	0	1	1	2	2	2	2	2
3	A	0	1	1	2	2	2	2	3
4	T	0	1	1	2	3	3	3	3
5	T	0	1	1	2	3	3	3	3
6	C	0	1	1	2	3	4	4	4
7	A	0	1	1	2	3	4	4	5
8	G	0	1	2	2	3	4	5	5
9	T	0	1	2	2	3	4	5	5
10	T	0	1	2	2	3	4	5	5
11	A	0	1	2	3	3	4	5	6

Tabla 3. Recuperación de la solución.

Alineamiento:
[x=11,y=7], [x=10,y=6], [x=9,y=6], [x=8,y=6], [x=7,y=5], [x=6,y=5], [x=5,y=4], [x=4,y=4], [x=3,y=3], [x=2,y=3], [x=1,y=2], [x=1,y=1], [x=0,y=0]

G¬AATTCAGTTA
GGA¬T¬C¬G¬¬A

Referencias:

The Needleman-Wunsch algorithm (J. Mol. Biol. 48, 443-453 [1970])

			1	2	3	4	5	6	7
			G	G	A	T	C	G	A
		0	0	0	0	0	0	0	0
1	G	0	1	1	1	1	1	1	1
2	A	0	1	1	2	2	2	2	2
3	A	0	1	1	2	2	2	2	3
4	T	0	1	1	2	3	3	3	3
5	T	0	1	1	2	3	3	3	3
6	C	0	1	1	2	3	4	4	4
7	A	0	1	1	2	3	4	4	5
8	G	0	1	2	2	3	4	5	5
9	T	0	1	2	2	3	4	5	5
10	T	0	1	2	2	3	4	5	5
11	A	0	1	2	3	3	4	5	6

			1	2	3	4	5	6	7
			G	G	A	T	C	G	A
		0	0	0	0	0	0	0	0
1	G	0	1	1	1	1	1	1	1
2	A	0	1	1	2	2	2	2	2
3	A	0	1	1	2	2	2	2	3
4	T	0	1	1	2	3	3	3	3
5	T	0	1	1	2	3	3	3	3
6	C	0	1	1	2	3	4	4	4
7	A	0	1	1	2	3	4	4	5
8	G	0	1	2	2	3	4	5	5
9	T	0	1	2	2	3	4	5	5
10	T	0	1	2	2	3	4	5	5
11	A	0	1	2	3	3	4	5	6

			1	2	3	4	5	6	7
			G	G	A	T	C	G	A
		0	0	0	0	0	0	0	0
1	G	0	1	1	1	1	1	1	1
2	A	0	1	1	2	2	2	2	2
3	A	0	1	1	2	2	2	2	3
4	T	0	1	1	2	3	3	3	3
5	T	0	1	1	2	3	3	3	3
6	C	0	1	1	2	3	4	4	4
7	A	0	1	1	2	3	4	4	5
8	G	0	1	2	2	3	4	5	5
9	T	0	1	2	2	3	4	5	5
10	T	0	1	2	2	3	4	5	5
11	A	0	1	2	3	3	4	5	6

			1	2	3	4	5	6	7
			G	G	A	T	C	G	A
		0	0	0	0	0	0	0	0
1	G	0	1	1	1	1	1	1	1
2	A	0	1	1	2	2	2	2	2
3	A	0	1	1	2	2	2	2	3
4	T	0	1	1	2	3	3	3	3
5	T	0	1	1	2	3	3	3	3
6	C	0	1	1	2	3	4	4	4
7	A	0	1	1	2	3	4	4	5
8	G	0	1	2	2	3	4	5	5
9	T	0	1	2	2	3	4	5	5
10	T	0	1	2	2	3	4	5	5
11	A	0	1	2	3	3	4	5	6

			1	2	3	4	5	6	7
			G	G	A	T	C	G	A
		0	0	0	0	0	0	0	0
1	G	0	1	1	1	1	1	1	1
2	A	0	1	1	2	2	2	2	2
3	A	0	1	1	2	2	2	2	3
4	T	0	1	1	2	3	3	3	3
5	T	0	1	1	2	3	3	3	3
6	C	0	1	1	2	3	4	4	4
7	A	0	1	1	2	3	4	4	5
8	G	0	1	2	2	3	4	5	5
9	T	0	1	2	2	3	4	5	5
10	T	0	1	2	2	3	4	5	5
11	A	0	1	2	3	3	4	5	6

			1	2	3	4	5	6	7
			G	G	A	T	C	G	A
		0	0	0	0	0	0	0	0
1	G	0	1	1	1	1	1	1	1
2	A	0	1	1	2	2	2	2	2
3	A	0	1	1	2	2	2	2	3
4	T	0	1	1	2	3	3	3	3
5	T	0	1	1	2	3	3	3	3
6	C	0	1	1	2	3	4	4	4
7	A	0	1	1	2	3	4	4	5
8	G	0	1	2	2	3	4	5	5
9	T	0	1	2	2	3	4	5	5
10	T	0	1	2	2	3	4	5	5
11	A	0	1	2	3	3	4	5	6