cap. 2 alineamiento

• INICIO
• DESCRIPCIÓN
  • JUSTIFICACIÓN
• CONTENIDO
• IDENTIFIQUESE
• APLICACIONES
• LECTURAS
• AYUDAS
  • ENLACES
  • GLOSARIO
  • BIBLIOGRAFÍA
• SERVICIOS
  • EMAIL
• CONTACTO

 

ALINEAMIENTO LOCAL DE UN PAR DE SECUENCIAS POR MEDIO DEL ALGORITMO DE SMITH & WATERMAN

El algoritmo de Smith and Waterman (1981) encuentra el segmento mejor alineado entre un par de secuencias.

Descripción:

Dadas dos secuencias A y B. 

A=a₁a₂...a_n y B=b₁b₂...b_m 

Se define:

• Una función de similitud (coincidencias) S(ai,bj) entre los elementos ai y bj de las secuencias a alinear, si las secuencias son proteínas se puede utilizar una matriz de sustitución como la PAM250 .
• Los in/dels (inserciones o deleciones) de longitud k se penalizan con un peso W_k. 
  Para la optimización de la penalización de los gap (W_k) se puede utilizar cualquiera de los siguientes modelos, los cuales son complementarios y no excluyentes:
1. definir una penalización por el usuario.
2. implementar una penalización logaritmica de la forma W=A + B * log(N), donde A y B son definidos por el usuario y N representa la longitud del hueco.
3. una penalización afin de la forma W=A + B * N, donde A y B son definidos por el usuario y N representa la longitud del hueco.
4. una ley de penalización de la forma W= A + B * N^C
   
   
• Se construye una matriz H de n+1 filas y m+1 columnas. (La secuencia A se ubica en las filas y la secuencia B en las columnas)

Características:

1. A las no coincidencias se le asigna un puntaje (peso) negativo.
2. El mínimo puntaje guardado en la matriz debe ser cero.
3. El inicio y final de un camino óptimo puede encontrarse en cualquier sitio de la matriz , no solo en la última fila o columna.
4. El puntaje se incrementa en una región de alta similaridad y disminuye fuera de tales regiones.
5. Si hay dos segmentos de alta similaridad, entonces deben estar lo suficientemente cercanos para que puedan encadenarse por un hueco o quedarán como segmentos independientes de similaridad local.
6. Cada segmento de similaridad debe iniciar con un puntaje de cero.
7. Se debe buscar en toda la matriz las regiones de alta similaridad local.
   

Procedimiento:

Figura 1. Cálculo del valor de H_ij

1. Se inicializa la matriz H con ceros.
2. La posición H_ij es la máxima similitud de dos segmentos que terminan en ai y bj respectivamente.  Y se obtiene de la siguiente expresión:

   H_ij = max { H_i-1,j-1 + S(a_i,b_j)  , max_k>1 {H_i-k,j - W_k}, max_l>1 {H_i,j-l - W_l } , 0 }   

   con  1<i<n y 1<j<m  y W_k = A + B*k     W_l = A + B* l. 

El segmento mejor alineado se obtiene de la matriz H ubicando en esta matriz la posición con el valor más alto y por medio de un procedimiento traceback se recuperan los residuos que conforman el segmento, el traceback se detiene cuando encuentra un cero en la diagonal de la matriz. Este procedimiento se puede aplicar de nuevo a la matriz con el fin de recuperar un nuevo segmento alineado.

Por ejemplo, si se tienen las siguientes secuencias:

Secuencia A: CAGCCUCGCUUAG,  m= 13
Secuencia B: AAUGCCAUUGACGG, n= 14

Parámetros:

• S(a_i,b_j) = 1 si a_i = b_j
• S(a_i,b_j) = -1/3 si a_i es diferente de b_j.
• W_k = 1 + 1/3 * k 
• W_l = 1 + 1/3 * l 

El máximo score de la matriz H (Tabla 1) es 3.3 y se encuentra en la posición (10,8); a partir de este sitio se empieza a recorrer la matriz hacia atrás (camino en rojo) hasta se encuentra un cero en la diagonal (posición (3,2)).

El segmento alineado es:

Este algoritmo fue modificado mas tarde por Waterman y Eggert en 1987.  La modificación fue la siguiente:

H_ij = max { H_i-1,j-1 + S(a_i,b_j)  , E_ij , F_ij , 0 }   

E_ij  = max {H_i,j-l - (u+v),  E_i,j-l - v }

F_ij = max {H _i-l,j - (u+v),  F_i-l,j - v }

Donde l es el tamaño posible del indels.

REFERENCIAS:

• IDENTIFICATION FOR COMMON MOLECULAR SUBSEQUENCES.  Smith & Waterman. 1981. Journal of Molecular Biology 147: 195-197.
• RAPID AND SENSITIVE PROTEIN SIMILARITY SEARCHES. Lipman and Pearson. 1985. Science 127: 1435-1441.

 

Carrera 30 No 45-03 - Edificio 477
Bogotá D.C. - Colombia

PBX: 3165000
webmaster@unal.edu.co
Aviso Legal - Copyright