Algoritmo Smith-Waterman

Por Germán González

El algoritmo Smith-Waterman es un famoso algoritmo para realizar alineamientos locales de secuencias; esto es, determinar regiones similares entre dos secuencias de nucleótidos o proteínas.

El algoritmo fue propuesto por Temple Smith y Michael Waterman en 1981. Como el algoritmo Needleman-Wunsch, del cual es una variación, Smith-Waterman es un algoritmo de programación dinámica. Como tal, posee la atractiva propiedad que garantiza encontrar el alineamiento local óptimo con respecto al sistema de puntaje que está siendo utilizado (que incluye la matriz de sustitución y el plan de puntaje con interrupciones).

La principal diferencia con el algoritmo Needleman-Wunsch es que las celdas negativas de las matrices de puntaje son puestas en cero, lo cual representa que los alineamientos locales sean visibles (y así claramente los puntajes).

El retroceso comienza en la celda de la matriz con el puntaje más alto y continua hasta que una celda con puntaje cero es encontrada, proporcionando el puntaje más alto para el alineamiento local.

Una motivación para alineamientos locales es la dificultad para obtener alineamientos correctos en regiones de baja similitudentre secuencias biológicas lejanamente emparentadas, porque las mutaciones agregaron mucho “ruido” con la evolución para permitir una comparación significativa de estas regiones. Los alineamientos locales evitan estas regiones completamente y se concentran en aquellas con un puntaje positivo, por ejemplo, aquellas con señales de similitud conservadas por la evolución. Una prerrequisito para alineamientos locales es una expectativa de puntaje negativo. La expectativa de puntaje es definida como el puntaje promedio que el sistema de puntaje (matriz de sustitución y penalidades por huecos) puede proporcionar para una secuencia aleatoria.

Otro motivo para usar alineamientos locales es que existe un modelo estadístico confiable (desarrollado por Karlin y Altschul) para alineamientos locales óptimos. El alineamiento de secuencias no relacionadas tiende a producir puntajes de alineamiento local óptimos que siguen una distribución de valores extrema. Esta propiedad permite a los programas producir un valor esperado para el alineamiento óptimo de dos secuencias, el cual es una medida de la frecuencia con que dos secuencias podrían producir un alineamiento óptimo cuyo puntaje es mayor o igual al puntaje observado. Valores muy bajos de expectativa indican que las dos secuencias pueden ser homólogas, lo que significa que podrían tener un ancestro en común.

Sin embargo, el algoritmo Smith-Waterman es bastante demandante de recursos de tiempo y memoria: para alinear dos secuencias de longitudes m y n, el tiempo y el espacio requerido son O(mn). Como resultado, en el uso práctico es reemplazado principalmente por el algoritmo BLAST que si bien no garantiza encontrar los alineamientos óptimos, es mucho más eficiente.

 

Comentarios