ALINEAMIENTO DE DOS SECUENCIAS (pairwise alignment) El alineamiento de una pareja de secuencias permite cuantificar el grado de similitud que hay entre ellas y determinar si existe algún tipo de relación entre ambas. Para alinear dos secuencias (X e Y), de longitud n y m, respectivamente, se coloca una encima de la otra de modo que el número de símbolos que coinciden en una misma posición sea máximo. Si es necesario, se pueden introducir huecos (indels) en una de las secuencias para que aumente el número de coincidencias. Al alinear dos secuencias, puede ocurrir que una misma posición esté ocupada por: •

residuos idénticos (match): Se supone que estos residuos formaban parte de una secuencia ancestral de la que descienden ambas secuencias y que durante la evolución han permanecido invariables. La conservación de estos residuos indica que, probablemente, desempeñan un papel importante para el mantenimiento de la estructura y/o función de la molécula. En un alineamiento, el número de posiciones ocupadas por residuos idénticos determina la identidad entre las secuencias (sequence identity) y se expresa en %.

•

residuos distintos pero con propiedades bioquímicas parecidas: son las denominadas sustituciones conservativas. El número de posiciones ocupadas por residuos idénticos o con propiedades bioquímicas similares determina la similitud entre las secuencias (sequence similarity) y se expresa en %.

•

residuos distintos (mismatch): Se supone que en esta posición ha tenido lugar una mutación. Si desconocemos la secuencia ancestral, es imposible saber con seguridad en cuál de las dos secuencias se ha producido la mutación.

•

un residuo cualquiera en una de las secuencias y un indel en la otra: Esta circunstancia se puede deber a la inserción de un residuo en una de las secuencias (insertion) o a la desaparición de un residuo en la otra (deletion).

Dos secuencias siempre se pueden alinear y puede haber muchos alineamientos posibles. Para determinar cuál es el mejor se utiliza un sistema de puntuación (como, por ejemplo, una matriz de sustitución) que otorga una puntuación distinta a cada pareja de caracteres en función de que sean iguales (match), distintos (mismatch) o haya un indel. Además, en caso se que sean distintos, se otorga a las sustituciones conservativas mayor puntuación que a las mutaciones. La puntuación de un alineamiento se calcula sumando la puntuación de cada una de las posiciones. El alineamiento que obtiene la mayor puntuación se denomina alineamiento óptimo. Si hay más de un alineamiento con la misma puntuación máxima (o muy parecida), será tarea del investigador decidir cuál es el que tiene mayor significado biológico. Además de la puntuación, también es importante estimar la significación estadística del resultado para determinar si las dos secuencias están realmente relacionadas o si su parecido es fruto del azar. Para comparar dos secuencias se pueden usar varios métodos: •

El algoritmo de la fuerza bruta

• • •

La matriz de puntos (dot-plot) Algoritmos de programación dinámica: el algoritmo de Needleman-Wunsch (para alineamientos globales) y el algoritmo de Smith-Waterman (para alineamientos locales) Métodos heurísticos como los algoritmos FASTA o BLAST

El algoritmo de la fuerza bruta Este algoritmo intenta encontrar la secuencia común de mayor tamaño entre dos secuencias X e Y de longitudes m y n, respectivamente. Para ello se consideran todas las subsecuencias posibles de X (2m) y se comparan con todas las subsecuencias posibles de Y (2n). En total hay que hacer 4 m+n comparaciones. Si se acepta la presencia de indels, hay que repetir los cálculos (m + n) veces para examinar la presencia de indels en todas las posiciones posibles de las dos secuencias. En la práctica, este método resulta imposible, tanto por el tiempo que se necesita como por los recursos de memoria que le harían falta al ordenador. Matrices de puntos (dot-plot) Este método fue descrito por vez primera en 1970 por Gibbs y McIntyre. Es un tipo de representación sencilla que encuentra todas las coincidencias existentes entre los residuos de las dos secuencias y ofrece una panorámica rápida del parecido que hay entre ellas. Será tarea del investigador determinar cuáles son relevantes y cuáles no.

Debe ser nuestra primera opción a la hora de comparar dos secuencias ya que permite detectar rápidamente las regiones similares. Es una buena forma de asegurarse de que no vamos a pasar por alto ninguna característica obvia. Aunque este método es de gran utilidad cuando el parentesco entre las secuencias es lejano, es capaz de identificar algunas relaciones complejas entre las secuencias como, por ejemplo, dominios proteicos repetidos o con el orden alterado, regiones palindrómicas, etc. que, de otra forma, serían difíciles de detectar.

Para realizar este tipo de análisis, se construye una matriz en la cual se coloca una de las secuencias en la parte superior (1ª fila) y la otra en la parte izquierda (1ª columna). La matriz se va rellenando con puntos en aquellas coordenadas (vertical/horizontal) en las que ambas secuencias contienen el mismo residuo. En muchos casos, sobre todo cuando las secuencias son de ADN, aparecen muchos puntos por simple azar y se genera mucho ruido, lo que dificulta la identificación de las regiones de similitud. Esto se puede corregir fácilmente mediante un filtrado de los datos. Para filtrar los datos se utilizan ventanas deslizantes. Se colocará un punto (en el centro de la ventana) únicamente si entre ambas ventanas existe un número mínimo de coincidencias. La ventana deslizante se define mediante dos parámetros: • •

El tamaño de la ventana (t) (suele ser 15 para el DNA y 2 ó 3 para proteínas) La rigor (r) es el número mínimo de coincidencias que debe haber entre las dos ventanas (suele ser 10 para el DNA y 2 para proteínas) para introducir un punto en la matriz.

Es importante seleccionar correctamente los valores de estos dos parámetros para detectar las regiones de interés. En general, hay que utilizar una ventana del tamaño del elemento que quiero localizar: • •

Cuando se comparan secuencias de DNA se usan ventanas largas y rigor elevado (t = 15 y r = 11, por ejemplo) Cuando se comparan secuencias de proteínas, si no se quiere usar el filtro se utilizan los valores t =1 y r = 1. Para filtrar las secuencias se usan ventanas cortas y rigor reducido (t = 2 y r = 2 o t = 3 y r = 2, por ejemplo). Para encontrar dominios cortos con similitud parcial en secuencias que no son muy parecidas (centros activos, por ejemplo) se usan ventanas más largas y algo más de rigor (t = 20 y r = 5, por ejemplo). También es posible utilizar matrices de puntuación.

Una vez rellenada la matriz: • • • • •

Cualquier región con secuencias similares aparece como una diagonal Los indel se manifiestan como desplazamientos de la diagonal: si se compara un mRNA con su DNA genómico se pueden diferenciar los intrones y los exones. La transposición de regiones del gen también se manifiestan como un desplazamiento de la diagonal Las regiones repetidas aparecen como diagonales paralelas a la diagonal principal (si son duplicaciones o repeticiones directas) o perpendiculares a la diagonal principal (si son repeticiones inversas) Las secuencias palindrómicas dan lugar a una línea perpendicular a la diagonal principal. Estas regiones pueden corresponder a (1) secuencias reconocidas por reguladores de la transcripción o por enzimas de restricción, (2) regiones complementarias del DNA o del RNA que adoptan una estructura secundaria (stem-loop) o (3) transposones de plantas

Una característica importante de las matrices de puntos es que permiten comparar una secuencia consigo misma. En este caso: • • • • •

Hay una diagonal de lado a lado Hay simetría respecto a esa diagonal Las líneas que aparezcan a ambos lados de la diagonal (arriba-abajo o derechaizquierda) indican repeticiones de la secuencia Las secuencias palindrómicas y las repeticiones invertidas aparecen como líneas perpendiculares a la diagonal Las áreas con una elevada densidad de puntos (con aspecto de cuadrado o de rectángulo) corresponden a secuencias repetidas o a regiones de poca complejidad en las que sólo están presentes unos pocos aminoácidos. Estas regiones complican los alineamientos porque originan alineamientos con una puntuación inusualmente elevada. Hay programas que detectan estas secuencias y las filtran para que no sean tenidas en cuenta.

EL ALGORITMO DE PROGRAMACIÓN DINÁMICA El algoritmo de programación dinámica es un método computacional que se basa en el principio de que para llegar a la solución óptima de un problema se pueden utilizar las soluciones óptimas de subproblemas más sencillos. Consideremos, por ejemplo, el diagrama de la figura inferior. A cada tramo del diagrama se le asigna una puntuación y queremos encontrar la ruta menos costosa que nos lleva desde la salida hasta la meta pasando por el punto A.

Para ir desde la salida hasta el punto A podemos seguir 6 rutas distintas. Análogamente, para ir desde el punto A hasta la meta hay otras 6 rutas distintas. Por lo tanto, hay 36 rutas distintas que llevan de la salida hasta la meta pasando por el punto A. ¿Es necesario evaluar cada una de las 36 rutas para determinar cuál es la menos costosa? La respuesta es que no. Esta es la observación crucial del asunto, ya que la elección de la mejor ruta para ir desde la salida hasta el punto A es independiente de la elección de la mejor ruta para ir desde el punto A hasta la meta. Si determinamos por un lado la mejor ruta para ir desde la salida hasta el punto A y, por otro lado, la mejor ruta para ir desde el punto A hasta la meta resulta que la mejor ruta para ir desde la salida hasta la meta es la suma de las dos anteriores. Por lo tanto, sólo es preciso evaluar 12 rutas, no las 36 posibles (que es lo que haría el algoritmo de fuerza bruta). El problema

aún se puede simplificar más si, de manera sistemática, dividimos el problema en más subproblemas. El algoritmo de programación dinámica se puede utilizar para alinear dos secuencias de ácidos nucleicos o de proteínas. Resulta particularmente importante porque permite encontrar el alineamiento óptimo ya que el problema de encontrar el alineamiento óptimo entre dos secuencias de longitud n se puede dividir en subproblemas más sencillos (encontrar el alineamiento óptimo de dos secuencias de longitud n-1, n-2, etc). El algoritmo de programación dinámica permite hacer alineamientos globales (algoritmo de Needleman-Wunsch) o alineamientos locales (algoritmo de SmithWaterman). Las diferencias entre un tipo de alineamiento y otro son mínimas. Para saber cuál de los dos tipos de alineamiento es el más apropiado hay que tener claro cuál es el objetivo que se persigue (descubrir motivos estructurales parecidos, decidir si son o no miembros de una misma familia o determinar si proceden de un mismo ancestro común). En función de este objetivo, tendré que decidir qué tipo de alineamiento debo realizar (global o local), qué algoritmo hay que utilizar (NeedlemanWunsch o Smith-Waterman) y qué sistema de puntuación (la matriz de sustitución y las penalizaciones por indels) es el más apropiado. Algoritmo de Needleman-Wunsch para alineamientos globales En 1970, Needleman y Wunsch diseñaron el primer algoritmo para hacer un alineamiento global de dos secuencias. Es un algoritmo de programación dinámica porque garantiza la obtención del mejor alineamiento sin tener que realizar todos los alineamientos posibles entre las dos secuencias. Para saber cuál es el mejor alineamiento de dos secuencias (X e Y) de longitud m y n, respectivamente, es necesario definir un sistema de puntuación que favorezca las coincidencias y penalice las diferencias y los huecos. Veamos un ejemplo: Secuencia X: GTCCTAC (longitud = m = 7) (X1 = G, X2 = T, X3 = C,..., X7 = C). Secuencia Y: GTACGTATC (longitud = n = 9) (Y1 = G, Y2 = T, Y3 = A,..., Y9 = C). Sistema de puntuación: Coincidencias = (+ 1); Diferencias = (− 1); Indels = (− 2) El algoritmo se ejecuta en varias etapas: 1.- Inicialización: se construye una matriz (m+1) × (n+1). La secuencia X (─, X1, X2,.., Xm) encabeza cada fila y la secuencia Y (─, Y1, Y2, ..,Yn) encabeza cada columna. Cada casilla de la matriz posee unas coordenadas (i, j) donde i indica el número de la fila y j indica el número de la columna. La casilla (1,1) se rellena con un 0. Cada casilla de la primera fila se rellena sumando a la anterior la penalización por indel. Análogamente, cada casilla de la primera columna se rellena sumando a la anterior la penalización por indel.

2.- Rellenado de la matriz: En cada casilla (i, j) se coloca el valor S(i, j) que cumpla la siguiente condición:

S (i , j )

⎡ S ( i −1, j −1) + ( X i , Y j ) ⎤ ⎢ ⎥ = max ⎢ S ( i −1, j ) + ( X i , indel )⎥ ⎢ S ( i , j −1) + (indel , Y j ) ⎥ ⎣ ⎦

(Xi,Yj) = +1 (si coinciden los caracteres) () (Xi,Yj) = −1 (si los caracteres no coinciden) () (Xi, indel) = −2 (indel en secuencia Y) () (indel, Yj) = −2 (indel en secuencia X) ()

En la casilla (2, 2) el valor que se introduce es el máximo de las tres posibilidades, que son: +1 (la suma de 0 y la puntuación de una coincidencia, flecha inclinada); −4 (la suma de −2 y la puntuación de un indel en la secuencia Y, flecha vertical) y −4 (la suma de −2 y la puntuación de un indel en la secuencia X, flecha horizontal). El valor máximo es +1. Para las etapas siguientes hay que recordar que al valor +1 se ha llegado desde el valor 0 (se indica mediante una flecha punteada).

→

En la casilla (2, 3) el valor que se introduce es el máximo de las tres posibilidades, que son: −3 (la suma de −2 y la puntuación de una diferencia, flecha inclinada), −1 (la suma de +1 y la puntuación de un indel, flecha horizontal) y −6 (la suma de −4 y la puntuación de un indel, flecha vertical). El valor máximo es −1. Para las etapas siguientes hay que recordar que al valor −1 se ha llegado desde el valor +1 (se indica mediante una flecha punteada).

→ De esta forma se rellenan todas las casillas de la matriz. La puntuación máxima del alineamiento es la que aparece en la casilla inferior derecha: 3.

3.- Retorno (traceback): Consiste en encontrar la ruta que nos ha llevado a alcanzar la puntuación máxima. En esta etapa nos serán de gran ayuda las flechas punteadas que hemos ido colocando durante la etapa de rellenado. La ruta que nos ha llevado hasta el alineamiento óptimo es la que aparece sombreada en color azul claro en la tabla inferior.

En este caso hay dos alineamientos óptimos posibles entre las secuencias X e Y, ya que en la casilla (4, 5) hay un 0 que puede provenir de la casilla (4,4) introduciendo un indel en la secuencia X o de la casilla (3,3), aceptando una diferencia (mismatch). Los dos alineamientos encontrados son los siguientes: G │ G

T │ T

A

G

−

C │ C

A │ A

T

C

T │ T

−

C │ C

+1 +1

-2

+1

-1

+1 +1

-2

+1

G │ G

T │ T

A

G −

T │ T

A │ A

T

C

C │ C

−

C │ C

+1 +1

-1

+1

-2

+1 +1

-2

+1

(total = +1)

(total = +1)

En este caso será tarea del investigador decidir cuál de los dos alineamientos óptimos es el que tiene más sentido biológico (si es que alguno lo tiene). Algoritmo de Smith-Waterman para alineamientos locales

En 1981, Smith y Waterman diseñaron un algoritmo para hacer un alineamiento local de dos secuencias. El objetivo consiste en localizar pequeñas regiones de similitud local en dos secuencias que, aparentemente, no guardan ninguna relación entre sí. Estas

regiones conservadas suelen ser importantes para el mantenimiento de la estructura y/o función de las secuencias. Es una versión ligeramente modificada del algoritmo de Needleman y Wunsch y, por lo tanto, también es un algoritmo de programación dinámica que garantiza la localización de los fragmentos de las secuencias con mayor similitud local. Para saber cuál es el mejor alineamiento es necesario definir un sistema de puntuación que favorezca las coincidencias y penalice las diferencias y los huecos. Veamos un ejemplo: Secuencia X: GTACGTATC (longitud = n = 9) (X1 = G, X2 = T, X3 = A,..., X9 = C) Secuencia Y: CAGTATCGT (longitud = m = 9) (Y1 = C, Y2 = A, Y3 = G,..., Y9 = T) Sistema de puntuación: Coincidencias = (+ 1); Diferencias = (−1); Indels = (−2)

El algoritmo se ejecuta en tres etapas: 1.- Inicialización: se construye una matriz (m+1) × (n+1). La secuencia X (─, X1, X2,.., Xm) encabeza cada fila y la secuencia Y (─, Y1, Y2, ..,Yn) encabeza cada columna. Cada casilla de la matriz posee unas coordenadas (i, j) donde i indica el número de la fila y j indica el número de la columna. Las casillas de la primera fila y de la primera columna se rellenan con ceros. Esta es la primera diferencia con el algoritmo de Needleman y Wunsch para hacer alineamientos globales.

2.- Rellenado de la matriz: En cada casilla (i, j) se coloca el valor S (i, j) que cumpla la siguiente condición:

S (i , j )

0 ⎡ ⎤ ⎢S ⎥ ( i −1, j −1) + ( X i , Y j ) ⎥ ⎢ = max ⎢ S ( i −1, j ) + ( X i , indel )⎥ ⎢ ⎥ ⎣⎢ S (i , j −1) + (indel , Y j ) ⎦⎥

(Xi,Yj) = +1 (si coinciden los caracteres) () (Xi,Yj) = −1 (si los caracteres no coinciden) () (Xi, indel) = −2 (indel en la secuencia Y) () (indel, Yj) = −2 (indel en la secuencia X) ()

Esta condición es la segunda diferencia con el algoritmo de Needleman y Wunsch. Al eliminar los valores negativos sustituyéndolos por un 0, se ponen de manifiesto las diversas regiones de similitud local. En la casilla (2, 2) el valor que se introduce es el máximo de las cuatro posibilidades, que son: 0, −1 (la suma de 0 y la puntuación de una diferencia, flecha inclinada); −2 (la suma de 0 y la puntuación de un indel en la secuencia Y, flecha vertical) y −2 (la suma de 0 y la puntuación de un indel en la secuencia X, flecha horizontal). El valor máximo es 0. Para recordar que a este valor se ha llegado desde la casilla (1,1) colocamos una flecha punteada.

→ De esta forma se rellenan todas las casillas de la matriz. La puntuación máxima del alineamiento puede aparecer en cualquier casilla. En este caso es un 5 (casilla sombreada en azul claro).

3.- Rastreo (traceback): Consiste en encontrar la ruta que nos ha llevado a alcanzar la puntuación máxima. En esta etapa nos serán de gran ayuda las flechas punteadas que hemos ido colocando durante la etapa de rellenado de la matri