Algoritmo Smith-Waterman

El algoritmo de Smith-Waterman es una reconocida estrategia para realizar alineamiento local de secuencias biológicas (ADN, ARN o proteínas); es decir que determina regiones similares entre un par de secuencias.

Ejemplo del algoritmo de Smith-Waterman. Las flechas azules indican el camino en la matriz, las rojas el alineamiento óptimo

El algoritmo SW fue propuesto por Temple Smith y Michael Waterman en 1981.[1]​ Está basado en el uso de algoritmos de programación dinámica, de tal forma que tiene la deseable propiedad de garantizar que el alineamiento local encontrado es óptimo con respecto a un determinado sistema de puntajes que se use (tales como matrices de substitución).

Las alternativas básicas para realizar el alineamiento de un par de secuencias son: el alineamiento local y el alineamiento global.

Los alineamientos globales pretenden alinear cada símbolo (o residuo) en cada secuencia. Esta estrategia es especialmente útil cuando las secuencias a alinear son altamente similares y aproximadamente del mismo tamaño. En contraste, los alineamientos locales son más útiles cuando las secuencias a alinear poseen grandes diferencias, pero se sospecha que existen regiones de similitud.

Algoritmo

editar

Sean   y   las dos secuencias biológicas a alinear, cuyas longitudes son   y   respectivamente. La puntuación de similitud entre dos elementos   y   está dada por  . A cada eliminación de longitud   se le asigna una penalización  .

  1. Para encontrar un par de segmentos con una gran similitud, se construye una matriz   de  × , inicializando la primera columna y primer fila con valores de  .
     .
  2. Cada valor   representa la máxima similitud entre dos segmentos que terminan en   y   respectivamente. Dichos valores se obtienen de la siguiente relación de recurrencia:
     
    donde
      es la puntuación de alinear   y  ,
      es la puntuación si   se encuentra al final de una eliminación de longitud  ,
      es la puntuación si   se encuentra al final de una eliminación de longitud  ,
      indica que no existe alguna similitud entre   y  , se añade este valor para evitar valores negativos.
  3. Para recuperar el par de segmentos con máxima similitud, se lleva a cabo un rastreo reverso a partir del máximo elemento de   hasta terminar en un elemento cuyo valor sea igual a  , siendo este el inicio de la alineación local óptima.

Complejidad algorítmica

editar

El algoritmo de Smith-Waterman tiene una complejidad temporal de   y una complejidad espacial de  . Esto representa una disminución considerable del costo computacional con respecto al enfoque de fuerza bruta, que tiene un tiempo de ejecución de   debido a que existen   y  subsecuencias de   y   respectivamente. No obstante, su complejidad representa una desventaja en comparación a la del algoritmo de Needleman-Wunsch,[2]​ que tiene una complejidad lineal. Especialmente cuando el valor de   es muy grande. Es por ello que se desarrollaron alternativas con un tiempo de ejecución lineal[3][4]​ y otros con complejidad espacial lineal con respecto a   .[5]

Ejemplo

editar

Sean  :AAGGCT y  :AACCCG las dos secuencias a alinear con una puntuación de similitud está dada por la siguiente relación:

 .

La matriz de puntuación se inicializa con   para todos los elementos de la primera columna y la primera fila. Después se calculan todas las puntuaciónes entre   y   , comenzando por   y  , denotado con amarillo en la siguiente matriz.

A A C C C G
0 0 0 0 0 0 0
A 0 1
A 0
G 0
G 0
C 0
T 0

Una vez calculados todos los valores se busca el elemento con la máxima puntuación, denotado con verde.

A A C C C G
0 0 0 0 0 0 0
A 0 1 1 0 0 0 0
A 0 1 2 1 0 0 0
G 0 0 1 1 0 0 1
G 0 0 0 0 0 0 1
C 0 0 0 1 1 1 0
T 0 0 0 0 0 0 0

Finalmente, para recuperar la alineación local óptima de   y   se lleva a cabo un rastreo a partir de ese elemento hasta llegar a un elemento con valor de  .

A A C C C G
0 0 0 0 0 0 0
A 0 1 1 0 0 0 0
A 0 1 2 1 0 0 0
G 0 0 1 1 0 0 1
G 0 0 0 0 0 0 1
C 0 0 0 1 1 1 0
T 0 0 0 0 0 0 0

La alineación resultante de este ejemplo consiste en alinear únicamente los primeros dos elementos de cada secuencia.

AA
||
AA

Penalización por huecos

editar

Penalización lineal

editar

La penalización por huecos sirve para determinar la puntuación de un indel, es decir, una inserción o una eliminación. El algoritmo de Smith-Waterman emplea una penalización lineal por extender la longitud de un hueco, donde la penalizacion   depende únicamente de la longitud   del hueco y del costo  de un hueco de un solo espacio :  .

Huecos afines

editar

Gotoh propuso un modelo de huecos afines, que consiste en modificar la penalizacion   para que esta sea función de dos parámetros:  , donde   es la penalización por extender un hueco,   es la penalización por iniciar un hueco y   es la longitud del hueco. Este esquema se reduce a la penalización lineal cuando  . Este modelo ofrece dos ventajas: reducir el número de operaciones a   y permitir que se asigne un costo más alto por iniciar un hueco que por extenderlo. La última propiedad tiene importantes implicaciónes biológicas ya que una simple mutación puede ocasionar varios cambios en un segmento de una secuencia, por lo tanto la creación de un hueco suele tener mayor impacto que su longitud. La disminución en el costo computacional del algoritmo de Gotoh se debe a que este intenta encontrar solo una de las alineaciónes locales óptimas y no garantiza encontrar alguna, a diferencia de Smith-Waterman que busca encontrar todas por lo que siempre encuentra la alineación óptima.

El algoritmo de Gotoh emplea tres matrices de  :

  •  : puntuación por alinear   y  ,
  •  : puntuación por alinear   con un hueco,
  •  : puntuación por alinear   con un hueco

Estas matrices tienen la siguiente inicialización:

  •  ,
  •  ,
  •  ,
  •  

Los valores de estas matrices se obtienen de las siguientes relaciones de recurrencia:

  •  
  •  
  •  

Huecos convexos

editar

Waterman[6]​ propuso otro sistema de penalización aún más flexible. A diferencia del modelo de huecos afines donde los costos de iniciar y extender un hueco son constantes,   y   respectivamente, en la penalización de huecos convexos el costo de extender el hueco disminuye a medida que aumenta su longitud:  .

Véase también

editar

Referencias

editar
  1. Smith TF, Waterman MS (1981). «Identification of common molecular subsequences.». J Mol Biol. 147 (1): 195-7. PMID 7265238. [1]
  2. Saul B. Needleman; Christian D. Wunsch (1970). «A general method applicable to the search for similarities in the amino acid sequence of two proteins». Journal of Molecular Biology 48 (3): 443-453. PMID 5420325. doi:10.1016/0022-2836(70)90057-4. 
  3. Osamu Gotoh (1982). «An improved algorithm for matching biological sequences». Journal of Molecular Biology 162 (3): 705-708. PMID 7166760. doi:10.1016/0022-2836(82)90398-9. «10.1.1.204.203». 
  4. Stephen F. Altschul & Bruce W. Erickson (1986). «Optimal sequence alignment using affine gap costs». Bulletin of Mathematical Biology 48 (5–6): 603-616. PMID 3580642. S2CID 189889143. doi:10.1007/BF02462326. 
  5. Miller, Webb; Myers, Eugene (1988). «Optimal alignments in linear space». Bioinformatics 4 (1): 11-17. PMID 3382986. doi:10.1093/bioinformatics/4.1.11. «10.1.1.107.6989». 
  6. Michael S. Waterman (1984). «Efficient Sequence Alignment Algorithms». Journal of Theoretical Biology 108: 333-337. doi:10.1016/s0022-5193(84)80037-5. 

Enlaces externos

editar