Información

2.5: El algoritmo de Needleman-Wunsch - Biología

2.5: El algoritmo de Needleman-Wunsch - Biología



We are searching data for your request:

Forums and discussions:
Manuals and reference books:
Data from registers:
Wait the end of the search in all databases.
Upon completion, a link will appear to access the found materials.

Ahora usaremos la programación dinámica para abordar el problema más difícil de la alineación de secuencia general. El algoritmo que desarrollaremos en las siguientes secciones para resolver la alineación de secuencias se conoce como algoritmo de Needleman-Wunsch.

Programación dinámica frente a memorización

Antes de sumergirnos en el algoritmo, conviene hacer una nota final sobre la memorización. Al igual que el problema de Fibonacci, el problema de alineación de secuencias se puede resolver con un enfoque de arriba hacia abajo o de abajo hacia arriba.

en un enfoque recursivo de arriba hacia abajo podemos usar la memorización para crear un diccionario potencialmente grande indexado por cada uno de los subproblemas que estamos resolviendo (secuencias alineadas). Esto requiere (O left (n ^ {2} m ^ {2} right) ) espacio si indexamos cada subproblema por los puntos inicial y final de las subsecuencias para las que se necesita calcular una alineación óptima. La ventaja es que resolvemos cada subproblema como máximo una vez: si no está en el diccionario, el problema se calcula y luego se inserta en el diccionario para referencia adicional.

en un enfoque iterativo de abajo hacia arriba podemos utilizar la programación dinámica. Definimos el orden de cálculo de los subproblemas de tal manera que se calcula una solución a un problema una vez que se han resuelto los subproblemas relevantes. En particular, los subproblemas más simples vendrán antes que los más complejos. Esto elimina la necesidad de realizar un seguimiento de los subproblemas que se han resuelto (el diccionario en la memorización se convierte en una matriz) y garantiza que no haya trabajo duplicado (cada subalineación se calcula solo una vez).

Por lo tanto, en este caso particular, la única diferencia práctica entre la memorización y la programación dinámica es el costo de las llamadas recursivas incurridas en el caso de la memorización (el uso de espacio es el mismo).

Planteamiento del problema

Supongamos que tenemos una alineación óptima para dos secuencias (S_ {1 ldots n} ) y (T_ {1 ldots m} ) en las que Si coincide con Tj. La idea clave es que esta alineación óptima se compone de una alineación óptima entre ( left (S_ {1}, ldots, S_ {i-1} right) ) y ( left (T_ {1}, ldots, T_ {i-1} right) ) y una alineación óptima entre ( left (S_ {i + 1}, ldots, S_ {n} right) ) y ( left (T_ {j + 1}, ldots, T_ {m} right) ). Esto se sigue de un argumento de cortar y pegar: si una de estas alineaciones parciales es subóptima, entonces cortamos y pegamos una mejor alineación en lugar de la subóptima. Esto logra una puntuación más alta de la alineación general y, por lo tanto, contradice la optimización de la alineación global inicial. En otras palabras, cada subruta en una ruta óptima también debe ser óptima. Observe que las puntuaciones son aditivas, por lo que la puntuación de la alineación general es igual a la suma de las puntuaciones de las alineaciones de las subsecuencias. Esto supone implícitamente que los subproblemas de calcular las alineaciones de puntuación óptimas de las subsecuencias son independientes. Necesitamos motivar biológicamente que tal suposición conduzca a resultados significativos.

Espacio índice de subproblemas

Ahora necesitamos indexar el espacio de los subproblemas. Sea (F_ {i, j} ) la puntuación de la alineación óptima de ( left (S_ {1}, ldots, S_ {i} right) ) y ( left (T_ {1 }, ldots, T_ {i} right) ). El espacio de los subproblemas es ( left {F_ {i, j}, i in [0, | S |], j in [0, | T |] right } ). Esto nos permite mantener una ((m + 1) × (n + 1) ) matriz F con las soluciones (es decir, puntuaciones óptimas) para todos los subproblemas.

Optimismo local

Podemos calcular la solución óptima para un subproblema haciendo una elección localmente óptima basada en los resultados de los subproblemas más pequeños. Por lo tanto, necesitamos establecer una función recursiva que muestre cómo la solución a un problema dado depende de sus subproblemas. Y usamos esta definición recursiva para llenar la tabla F de forma ascendente.

Podemos considerar las 4 posibilidades (insertar, eliminar, sustituir, emparejar) y evaluar cada una de ellas en función de los resultados que hemos calculado para subproblemas más pequeños. Para inicializar la tabla, establecemos (F_ {0, j} = −j · d ) y (F_ {i, 0} = −i · d ) ya que esas son las puntuaciones de alinear ( left ( T_ {1}, ldots, T_ {i} right) ) con j espacios y ( left (S_ {1}, ldots, S_ {i} right) ) con (i ) espacios (también conocido como superposición cero entre las dos secuencias). Luego recorremos la matriz columna por columna calculando la puntuación óptima para cada subproblema de alineación considerando las cuatro posibilidades:

• La secuencia S tiene un espacio en la posición de alineación actual.

• La secuencia T tiene un espacio en la posición de alineación actual.

• Hay una mutación (sustitución de nucleótidos) en la posición actual.

• Hay una coincidencia en la posición actual.

Luego usamos la posibilidad que produce la máxima puntuación. Expresamos esto matemáticamente mediante la fórmula recursiva para (F_ {i, j} ):

[F (0,0) = 0 nonumber ]

[Inicialización: F (i, 0) = F (i - 1, 0) - d nonumber ]

[F (0, j) = F (0, j - 1) - d nonumber ]

[ text {Iteración}: quad F (i, j) = max left { begin {array} {l}
F (i-1, j) -d text {insertar espacio en S}
F (i, j-1) -d text {insertar espacio en T}
F (i-1, j-1) + s left (x_ {i}, y_ {j} right) text {coincidencia o mutación}
end {matriz} right. nonumber ]

Terminación: abajo a la derecha

Después de atravesar la matriz, la puntuación óptima para la alineación global viene dada por (F_ {m, n} ). El orden transversal debe ser tal que tengamos soluciones a determinados subproblemas cuando las necesitemos. Es decir, para calcular (F_ {i, j} ), necesitamos conocer los valores a la izquierda, arriba y diagonalmente arriba de (F_ {i, j} ) en la tabla. Por lo tanto, podemos recorrer la tabla en orden principal de fila o columna o incluso en diagonal desde la celda superior izquierda a la celda inferior derecha. Ahora, para obtener la alineación real, solo tenemos que recordar las elecciones que hicimos en cada paso.

Solucion optima

Los caminos a través de la matriz (F ) corresponden a alineaciones de secuencia óptimas. Al evaluar cada celda (F_ {i, j} ) hacemos una elección seleccionando el máximo de las tres posibilidades. Por lo tanto, el valor de cada celda (no inicializada) en la matriz está determinado por la celda a su izquierda, arriba de ella, o diagonalmente a la izquierda arriba de ella. Un partido y una sustitución se representan ambos viajando en la dirección diagonal; sin embargo, se puede aplicar un costo diferente para cada uno, dependiendo de si los dos pares de bases que estamos alineando coinciden o no. Para construir la alineación óptima real, necesitamos rastrear nuestras elecciones en la matriz. Es útil mantener un puntero para cada celda mientras se llena la tabla que muestra qué elección se tomó para obtener la puntuación de esa celda. Entonces podemos simplemente seguir nuestros indicadores hacia atrás para reconstruir la alineación óptima.

Análisis de solución

El análisis en tiempo de ejecución de este algoritmo es muy sencillo. Cada actualización toma (O (1) ) tiempo, y dado que hay mn elementos en la matriz F, el tiempo total de ejecución es (O (mn) ). De manera similar, el espacio total de almacenamiento es O (mn). Para el caso más general donde la regla de actualización es más complicada, el tiempo de ejecución puede ser más caro. Por ejemplo, si la regla de actualización requiere probar todos los tamaños de brechas (por ejemplo, el costo de una brecha no es lineal), entonces el tiempo de ejecución sería (O (mn (m + n)) ).

Needleman-Wunsch en la práctica

Supongamos que queremos alinear dos secuencias S y T, donde

S = AGT

T = AAGC

El primer paso es colocar las dos secuencias a lo largo de los márgenes de una matriz e inicializar las celdas de la matriz. Para inicializar, asignamos un 0 a la primera entrada de la matriz y luego completamos la primera fila y columna en función de la adición incremental de penalizaciones por espacio, como se muestra en la Figura 2.9 a continuación. Aunque el algoritmo podría completar la primera fila y columna a través de la iteración, es importante definir claramente y establecer límites al problema.

El siguiente paso es la iteración a través de la matriz. El algoritmo avanza a lo largo de filas o columnas, considerando una celda a la vez. Para cada celda se calculan tres puntajes, dependiendo de los puntajes de tres celdas de matriz adyacentes (específicamente la entrada de arriba, la que está en diagonal hacia arriba y hacia la izquierda, y la que está a la izquierda). La puntuación máxima de estos tres posibles rastreos se asigna a la entrada y también se almacena el puntero correspondiente. La terminación ocurre cuando el algoritmo llega a la esquina inferior derecha. En la Figura 2.10, la matriz de alineación para las secuencias S y T se ha completado con puntuaciones y punteros.

El paso final del algoritmo es el rastreo de ruta óptimo. En nuestro ejemplo, comenzamos en la esquina inferior derecha y seguimos los punteros disponibles hasta la esquina superior izquierda. Al registrar las decisiones de alineación tomadas en cada celda durante el rastreo, podemos reconstruir la alineación de secuencia óptima de principio a fin y luego invertirla. Tenga en cuenta que en este caso particular, existen múltiples vías óptimas (Figura 2.11). En el Apéndice 2.11.4 se incluye una implementación de pseudocódigo del algoritmo de Needleman-Wunsch.

Optimizaciones

El algoritmo dinámico que presentamos es mucho más rápido que la estrategia de fuerza bruta de enumerar alineaciones y funciona bien para secuencias de hasta 10 kilo-bases de longitud. Sin embargo, en la escala de alineaciones del genoma completo, el algoritmo dado no es factible. Para alinear secuencias mucho más grandes, podemos realizar modificaciones en el algoritmo y mejorar aún más su rendimiento.

Programación dinámica limitada

Una posible optimización es ignorar las alineaciones levemente aburridas (MBA) o alineaciones que tienen demasiados huecos. Explícitamente, podemos limitarnos a permanecer dentro de cierta distancia W de la diagonal en la matriz

F de subproblemas. Es decir, asumimos que la ruta de optimización en F desde (F_ {0,0} ) a (F_ {m, n} ) está dentro de la distancia W a lo largo de la diagonal. Esto significa que la recursividad (2.2) solo debe aplicarse a las entradas en F dentro de la distancia W alrededor de la diagonal, y esto produce un costo de tiempo / espacio de (O ((m + n) W) ) (consulte la Figura 2.12).

Sin embargo, tenga en cuenta que esta estrategia es heurística y ya no garantiza una alineación óptima. En cambio, alcanza un límite inferior en la puntuación óptima. Esto se puede utilizar en un paso posterior en el que descartamos las recursiones en la matriz F que, dado el límite inferior, no puede conducir a una alineación óptima.

Alineación de espacio lineal

La recursividad (2.2) se puede resolver usando solo espacio lineal: actualizamos las columnas en F de izquierda a derecha durante las cuales solo hacemos un seguimiento de la última columna actualizada que cuesta (O (m) ) espacio. Sin embargo, además de la puntuación (F_ {m, n} ) de la alineación óptima, también queremos calcular una alineación correspondiente. Si usamos el rastreo, entonces necesitamos almacenar punteros para cada una de las entradas en F, y esto cuesta (O (mn) ) espacio.

¡También es posible encontrar una alineación óptima utilizando solo espacio lineal! El objetivo es utilizar dividir y conquistar para calcular la estructura de la alineación óptima para una entrada de matriz en cada paso. La figura 2.13 ilustra el proceso. La idea clave es que una alineación de programación dinámica puede proceder con la misma facilidad en la dirección inversa, comenzando en la esquina inferior derecha y terminando en la esquina superior izquierda. Entonces, si la matriz se divide por la mitad, tanto una pasada hacia adelante como una pasada hacia atrás pueden ejecutarse al mismo tiempo y converger en la columna del medio. En el punto de cruce podemos sumar las dos puntuaciones de alineación; la celda de la columna del medio con la puntuación máxima debe estar en la ruta óptima general.

Podemos describir este proceso de manera más formal y cuantitativa. Primero calcule el índice de fila (u ∈ {1, ..., m} ) que está en la ruta óptima mientras cruza la columna ( frac {n} {2} th ). Para (1 ≤ i ≤ m ) y (n ≤ j ≤ n ) sea (C_ {i, j} ) el índice de fila que está en la ruta óptima a (F_ {i, j} ) mientras cruza la columna ( frac {n} {2} th ). Luego, mientras actualizamos las columnas de F de izquierda a derecha, también podemos actualizar las columnas de C de izquierda a derecha. Entonces, en (O (mn) ) tiempo y (O (m) ) espacio podemos calcular la puntuación (F_ {m, n} ) y también (C_ {m, n} ), que es igual al índice de fila (u ∈ {1,., m} ) que está en la ruta óptima mientras cruza la columna ( frac {n} {2} th ). Ahora entra en juego la idea de dividir y conquistar. Repetimos el procedimiento anterior para la submatriz (u times frac {n} {2} ) superior izquierda de F y también repetimos el procedimiento anterior para la ((( mu) times frac {n} {2} ) submatriz de F. Esto se puede hacer usando (O (m + n) ) espacio lineal asignado. El tiempo de ejecución para la submatriz superior izquierda es (O left ( frac {un} {2} right) ) y el tiempo de ejecución para la submatriz inferior derecha es (O left ( frac {(mu) n} {2} right) ), que sumados da un tiempo de ejecución de (O left ( frac {mn} {2} right) = O (mn) ).

Seguimos repitiendo el procedimiento anterior para submatrices cada vez más pequeñas de F mientras recopilamos más y más entradas de una alineación con una puntuación óptima. El tiempo de ejecución total es (O (mn) + O left ( frac {mn} {2} right) + O left ( frac {mn} {4} right) + ldots = O (2mn ) = O (mn) ). Por lo tanto, sin sacrificar el tiempo total de ejecución (hasta un factor constante), dividir y conquistar conduce a una solución de espacio lineal (ver también la Sección ?? de la Clase 3).


Detalles del algoritmo de Needleman-Wunsch

Intento comprender los detalles del algoritmo Needleman-Wunsch y utilizo un ejemplo del libro [Nello Cristianini, Matthew W. Hahn. Introducción a la genómica computacional. Un enfoque de estudios de caso, www.computational-genomics.net].

En mi opinión, el algoritmo no se describe muy claramente, por lo que surge la pregunta.

Además, el cálculo de la puntuación para el vecino diagonal también es claro,

porque esta es una alineación sin un espacio:

El momento poco claro es la alineación del vecino izquierdo (o superior). Di, el vecino de la izquierda


3.1 Algoritmos de alineación y programación dinámica

Uno de los primeros intentos de alinear dos secuencias fue llevado a cabo por Vladimir Levenstein en 1965, llamado "distancia de edición", y ahora a menudo se llama Distancia de Levenshtein. La distancia de edición se define como el número de ediciones de un solo carácter necesarias ”para cambiar una palabra a otra. Inicialmente, describió textos y palabras escritos, pero este método se aplicó luego a secuencias biológicas. Uno de los algoritmos más utilizados para calcular la distancia de edición es el algoritmo de Wagner-Fischer, un algoritmo de programación dinámica.

La programación dinámica enuncia de manera óptima el problema completo como la solución óptima para las piezas más pequeñas (subproblemas). Entonces, el problema general puede expresarse como una composición de los subproblemas. Además del algoritmo de Wagner-Fischer, se han desarrollado muchos otros algoritmos de programación dinámica para alinear secuencias biológicas, incluidos los algoritmos Needleman-Wunsch [22] y Smith-Waterman [23].


Algoritmos de alineación de secuencia

Los algoritmos de programación dinámica son algoritmos recursivos modificados para almacenar resultados intermedios, lo que mejora la eficiencia para ciertos problemas. El algoritmo Smith-Waterman (Needleman-Wunsch) utiliza un algoritmo de programación dinámica para encontrar la alineación local (global) óptima de dos secuencias, y. El algoritmo de alineación se basa en encontrar los elementos de una matriz donde el elemento es la puntuación óptima para alinear la secuencia (,.) Con (,.). Dos aminoácidos similares (por ejemplo, arginina y lisina) reciben una puntuación alta, dos aminoácidos diferentes (por ejemplo, arginina y glicina) reciben una puntuación baja. Cuanto mayor sea la puntuación de un camino a través de la matriz, mejor será la alineación. La matriz se encuentra encontrando progresivamente los elementos de la matriz, comenzando y procediendo en las direcciones de aumentar y. Cada elemento se configura de acuerdo con:

donde es la puntuación de similitud de comparar aminoácido con aminoácido (obtenido aquí de la tabla de similitud BLOSUM40) y es la penalización por un solo espacio. La matriz se inicializa con. Al obtener la alineación local Smith-Waterman, se modifica:

La penalización por espacio se puede modificar, por ejemplo, se puede reemplazar por, donde es la penalización por un solo espacio y es el número de espacios consecutivos.

Una vez que se encuentra la puntuación de alineación óptima, se encuentra el `` rastreo '' a lo largo de la ruta óptima, que corresponde a la alineación de secuencia óptima para la puntuación. En el siguiente conjunto de ejercicios, implementará manualmente la alineación de Needleman-Wunsch para un par de secuencias cortas, luego realizará alineaciones de secuencia global con un programa de computadora desarrollado por Anurag Sethi, que se basa en el algoritmo Needleman-Wunsch con una penalización de brecha afín ,, donde es la penalización por espacio de extensión. El archivo de salida estará en formato GCG, uno de los dos formatos estándar en bioinformática para almacenar información de secuencia (el otro formato estándar es FASTA).

Realice manualmente una alineación Needleman-Wunsch

En el primer ejercicio, probará el algoritmo de Smith-Waterman en una secuencia corta de partes de hemoglobina (código PDB 1AOW) y mioglobina 1 (código PDB 1AZI).

    Aquí alineará la secuencia HGSAQVKGHG con la secuencia KTEAEMKASEDLKKHGT.

H GRAMO S A Q V K GRAMO H GRAMO
0 -8 -16 -24 -32 -40 -48 -56 -64 -72 -80
K -8
T -16
mi -24
A -32
mi -40
METRO -48
K -56
A -64
S -72
mi -80
D -88
L -96
K -104
K -112
H -120
GRAMO -128
T -136

    El primer paso es completar las puntuaciones de similitud S al buscar las coincidencias en la tabla BLOSUM40, que se muestra aquí etiquetada con códigos de aminoácidos de 1 letra:

    Completamos los puntajes de similitud de BLOSUM40 para usted en la Tabla 4.

, utilizando la convención de que los valores aparecen en la parte superior de un cuadrado en letra grande y los valores aparecen en la parte inferior de un cuadrado en letra pequeña. Nuestra penalización por hueco es 8.

Nota: consideramos que es el `` predecesor '' de, ya que ayudó a decidir el valor. Más adelante, los predecesores calificarán para estar en la ruta de rastreo.

Tabla 4: Hoja de trabajo de puntuación de alineación. En todos los cuadros de alineación, se proporciona la puntuación de similitud de la búsqueda de la matriz BLOSUM40 (texto pequeño, parte inferior del cuadrado). Se proporcionan cuatro puntajes de alineación como ejemplos (texto grande, parte superior del cuadrado), intente calcular al menos cuatro más, siguiendo la dirección proporcionada en el texto para el cálculo.
H GRAMO S A Q V K GRAMO H GRAMO
0 -8 -16 -24 -32 -40 -48 -56 -64 -72 -80
K -8
T -16
mi -24
A -32
mi -40
METRO -48
K -56
A -64
S -72
mi -80
D -88
L -96
K -104
K -112
H -120
GRAMO -128
T -136
Tabla 5: Hoja de trabajo de rastreo. La matriz de puntuación de alineación completa (texto grande, parte superior de cada cuadrado) con las puntuaciones de búsqueda de BLOSUM40 S (texto pequeño, parte inferior de cada cuadrado). Para encontrar la alineación, retroceda comenzando desde la parte inferior derecha (T vs G, puntuación -21) y proceda en diagonal (hacia la izquierda y hacia arriba), hacia la izquierda o hacia arriba. Sin embargo, solo proceda si el cuadrado en esa dirección pudo haber sido un predecesor, de acuerdo con las condiciones descritas en el texto.
H GRAMO S A Q V K GRAMO H GRAMO
0 -8 -16 -24 -32 -40 -48 -56 -64 -72 -80
K -8
T -16
mi -24
A -32
mi -40
METRO -48
K -56
A -64
S -72
mi -80
D -88
L -96
K -104
K -112
H -120
GRAMO -128
T -136

    Ahora, para comparar sus resultados con un programa de computadora. Hemos preparado un programa de alineación de Needleman-Wunsch por pares, par, que aplicará a las mismas secuencias que acaba de alinear manualmente.

/tbss.work/Bioinformatics/pairData
luego inicie el ejecutable de alineación de pares escribiendo:
par targlist
. Todas las alineaciones se llevarán a cabo utilizando la matriz BLOSUM40, con una penalización por espacio de 8. Las rutas a los archivos de entrada y la matriz BLOSUM40 utilizada se definen en el archivo targlist. La matriz BLOSUM40 son las primeras 25 líneas del archivo blosum40. (Se pueden encontrar otras matrices de sustitución en el sitio web de NCBI / Blast).

Nota: En algunas instalaciones, el ejecutable del par es
en

/tbss.work/Bioinformatics/pairData y aquí debes
escriba ./pair targlist para ejecutarlo.
Si no puede acceder al ejecutable del par en absoluto, puede ver el resultado de este paso en

Encontrar pares homólogos de sintetasas de ARNt de clase II

Las proteínas homólogas son proteínas derivadas de un gen ancestral común. En este ejercicio con el algoritmo de Needleman-Wunsch, estudiará la identidad de secuencia de varias sintetasas de ARNt de clase II, que son de Eucarya, Eubacteria o Archaea o difieren en el tipo de reacción de aminoacilación que catalizan. La Tabla 6 resume el tipo de reacción, el organismo y el código de acceso de AP y el nombre de la cadena de los dominios de ARNt sintetasa de Clase II empleados.

Especificidad Organismo Código PDB: cadena Dominio catalítico ASTRAL
Aspartilo Eubacterias 1EQR: B d1eqrb3
Aspartilo Arqueas 1B8A: A d1b8aa2
Aspartilo Eukarya 1ASZ: A d1asza2
Glycl Arqueas 1ATI: A d1atia2
Histidilo Eubacterias 1ADJ: C d1adjc2
Lysl Eubacterias 1BBW: A d1bbwa2
Aspartilo Eubacterias 1EFW: A d1efwa3

    Hemos preparado un programa de computadora múltiple que alineará múltiples pares de proteínas.


Indel es un término que se utiliza tanto para las operaciones de inserción como de eliminación en secuencias biológicas.

Alsmirat MA, Jararweh Y, Al-Ayyoub M, Shehab MA, Gupta BB (2017) Aceleración de algoritmos de segmentación de imágenes médicas intensivas en computación utilizando implementaciones híbridas de cpu-gpu. Multimed Tools Appl 76 (3): 3537–3555

Balhaf K, Alsmirat MA, Al-Ayyoub M, Jararweh Y, Shehab MA (2017) Acelerando los algoritmos de distancia de edición de levenshtein y damerau usando gpu con memoria unificada. En: 2017 8a conferencia internacional sobre sistemas de información y comunicación (ICICS). IEEE, págs. 7–11

Balhaf K, Shehab MA, Wala’a T, Al-Ayyoub M, Al-Saleh M, Jararweh Y (2016) Uso de gpus para acelerar el cálculo de la distancia de edición de levenshtein. En: 2016 VII congreso internacional sobre sistemas de información y comunicación (ICICS). IEEE, págs. 80–84

Butenhof DR (1997) Programación con hilos POSIX. Addison-Wesley Professional, Boston

Chan S, Wong A, Chiu D (1992) Un estudio de múltiples métodos de comparación de secuencias. Bull Math Biol: 563–598

Cook S (2012) Programación CUDA: una guía para desarrolladores sobre computación paralela con GPU. Newnes, pág. 16-25

De Oliveira Sandes E, Miranda G, Martorell X, Ayguade E, Teodoro G, Magalhaes Alves de Melo AC (2016) Cudalign 4.0: rastreo especulativo incremental para una alineación exacta de todo el cromosoma en grupos de GPU. IEEE Trans Parallel Distrib Syst 27 (10): 2838–2850

Durbin R, Eddy S, Krogh A, Mitchison G (1998) Análisis de secuencia biológica. Prensa de la Universidad de Cambridge, Cambridge

El-Metwally S, Ouda O, Helmy M (2014) Tecnologías de secuenciación de próxima generación y desafíos en el ensamblaje de secuencias. Springer Sci Bus 7: 16–25

Fakirah M, Shehab MA, Jararweh Y, Al-Ayyoub M (2015) Acelerando el algoritmo de alineación global needleman-wunsch con gpus. En: 2015 IEEE / ACS 12th conferencia internacional de sistemas y aplicaciones informáticas (AICCSA). IEEE, págs. 1–5

Farrar M (2007) Striped smith-waterman acelera las búsquedas en bases de datos seis veces más que otras implementaciones de simd. Bioinformática 23 (2): 156–161

Gebali F (2011) Algoritmos y computación paralela, vol 84. Wiley, Nueva York

Gotoh O (1982) Un algoritmo mejorado para emparejar secuencias biológicas. J Mol Biol 162 (3): 705–708

Jones C, Pevzner P (2004) Una introducción a los algoritmos bioinformáticos. Prensa del MIT, Cambridge

Katoh K, Toh H (2008) Desarrollos recientes en el programa de alineación de secuencia múltiple mafft. Breve información biológica 92: 86–98

Liu Y, Schmidt B (2015) Gswabe: alineación de secuencia acelerada por gpu más rápida con recuperación de alineación óptima para secuencias de ADN cortas. Concurr Comput: Pract Exper 27 (4): 958–972

Lomont C (2011) Introducción a las extensiones vectoriales avanzadas de Intel. Libro blanco, Intel

Needleman SB, Wunsch CD (1970) Un método general aplicable a la búsqueda de similitudes en la secuencia de aminoácidos de dos proteínas. J Mol Biol 48 (3): 443–453

Rognes T (2011) Búsquedas más rápidas en la base de datos Smith-Waterman con paralelización SIMD entre secuencias. BMC Bioinform 12: 221. https://doi.org/10.1186/1471-2105-12-221

Rognes T, Seeberg E (2000) Sextuplicación de las búsquedas en bases de datos de secuencias de smith-waterman utilizando procesamiento paralelo en microprocesadores comunes. Bioinformática 16 (8): 699–706

Sanders J, Kandrot E (2010) CUDA por ejemplo: una introducción a la programación de GPU de propósito general. Addison-Wesley Professional, Boston

Serrano JP, De Oliveira Sandes E, Magalhaes Alves de Melo A, Ujaldon M (2017) Aceleración de Smith-waterman en multi-gpus: un análisis de rendimiento por vatio. En: Bioinformática e ingeniería biomédica - 5a conferencia internacional de trabajo, IWBBIO 2017, Granada, España, 26-28 de abril de 2017, Actas, Parte II, pp 512-523

Setubal J, Meidanis J (1997) Introducción a la biología molecular computacional. Pub PWS, Boston

Shehab MA, Al-Ayyoub M, Jararweh Y (2015) Mejora del rendimiento de los algoritmos fcm y t2fcm utilizando gpus para la segmentación de imágenes médicas. En: 2015 Sexta conferencia internacional sobre sistemas de información y comunicación (ICICS), págs. 130-135

Siriwardena P, Ranasinghe N (2010) Aceleración de la alineación de secuencia global usando gpu multinúcleo compatible con cuda. En: 5ª conferencia internacional en información y automatización para la sostenibilidad (ICIAFS), pp 201–206

Vermij P (2011) Alineación de secuencias genéticas en una plataforma de supercomputación. Tesis doctoral, TU Delft, Universidad Tecnológica de Delft

Wozniak A (1997) Uso de instrucciones orientadas a video para acelerar la comparación de secuencias. Comput Appl Biosci: CABIOS 13 (2): 145–150

Zhou W, Zhanxiu C, Lian B, Wang J, Jianping M (2017) Búsqueda en la base de datos de proteínas del algoritmo de alineación híbrida basado en la aceleración paralela de gpu. J Supercomputación. https://doi.org/10.1007/s11227-017-2030-x

Zhu X, Li K, Salah A, Shi L, Li K (2015) Implementación paralela de MAFFT en hardware gráfico habilitado para cuda. IEEE / ACM Trans Comput Biol Bioinform 12 (1): 205–218. https://doi.org/10.1109/TCBB.2014.2351801


Conclusión

Una eficiente heurística de alineación de secuencias de ARN por pares, que considera intrínsecamente los pares de bases subóptimos, discrimina con precisión entre distintas familias de ARN estructurado. Cuando se combina con un algoritmo de agrupación basado en densidad tolerante al ruido, este enfoque identifica motivos de estructura de ARN nuevos y conocidos a partir de un conjunto de secuencias de entrada sin conocimiento a priori. Los motivos de estructura de ARN resultantes se utilizan posteriormente para identificar homólogos en el genoma humano, mejorando la anotación de lncRNA y aumentando el repertorio de elementos genéticos funcionales.


Alineación e importancia de la secuencia:

Alineación de secuenciao la comparación de secuencias se encuentra en el corazón de la bioinformática, que describe la forma de disposición de las secuencias de ADN / ARN o de proteínas, con el fin de identificar las regiones de similitud entre ellas. Se utiliza para inferir la relación estructural, funcional y evolutiva entre las secuencias. La alineación encuentra el nivel de similitud entre la secuencia de consultas y las diferentes secuencias de la base de datos. El algoritmo funciona mediante un enfoque de programación dinámica que divide el problema en subproblemas independientes más pequeños. Encuentra la alineación de forma más cuantitativa asignando puntuaciones.

Cuando se encuentra una nueva secuencia, la estructura y función se pueden predecir fácilmente haciendo una alineación de secuencia. Dado que se cree que, una secuencia que comparte un ancestro común exhibiría una estructura o función similar. Cuanto mayor sea la similitud de secuencia, mayor es la posibilidad de que compartan una estructura o función similar.

Métodos de alineación de secuencias:

Existen principalmente dos métodos de alineación de secuencia:

Alineación global: Las secuencias estrechamente relacionadas que tienen la misma longitud son muy apropiadas para la alineación global. Aquí, la alineación se lleva a cabo desde el principio hasta el final de la secuencia para encontrar la mejor alineación posible.

El algoritmo Needleman-Wunsch (una fórmula o conjunto de pasos para resolver un problema) fue desarrollado por Saul B. Needleman y Christian D. Wunsch en 1970, que es un algoritmo de programación dinámica para la alineación de secuencias. La programación dinámica resuelve el problema original dividiendo el problema en subproblemas independientes más pequeños. Estas técnicas se utilizan en muchos aspectos diferentes de la informática. El algoritmo explica la alineación de secuencias global para alinear secuencias de nucleótidos o proteínas.

Alineación local: Las secuencias que se sospecha que tienen similitud o incluso secuencias diferentes pueden compararse con el método de alineación local. Encuentra regiones locales con alto nivel de similitud.

Estos dos métodos de alineación se definen mediante diferentes algoritmos, que utilizan matrices de puntuación para alinear las dos series diferentes de caracteres o patrones (secuencias). Los dos métodos de alineación diferentes se definen principalmente mediante un enfoque de programación dinámica para alinear dos secuencias diferentes.

Programación dinámica:

La programación dinámica se utiliza para una alineación óptima de dos secuencias. Encuentra la alineación de una manera más cuantitativa dando algunos puntajes para coincidencias y desajustes (matrices de puntaje), en lugar de solo aplicar puntos. Al buscar las puntuaciones más altas en la matriz, se puede obtener la alineación con precisión. La programación dinámica resuelve el problema original dividiendo el problema en subproblemas independientes más pequeños. Estas técnicas se utilizan en muchos aspectos diferentes de la informática. Los algoritmos de Needleman-Wunsch y Smith-Waterman para la alineación de secuencias se definen mediante un enfoque de programación dinámica.

Matrices de puntuación:

En los procedimientos de alineación óptimos, la mayoría de los algoritmos Needleman-Wunsch y Smith-Waterman utilizan un sistema de puntuación. Para el alineamiento de la secuencia de nucleótidos, las matrices de puntuación utilizadas son relativamente más simples ya que la frecuencia de mutación para todas las bases es igual. Se asigna un valor positivo o más alto para una coincidencia y un valor negativo o más bajo para la discrepancia. Estas puntuaciones basadas en supuestos se pueden utilizar para puntuar las matrices. Existen otras matrices de puntuación que están predefinidas en su mayoría, utilizadas en el caso de sustituciones de aminoácidos.

Las matrices predefinidas más utilizadas son PAM y BLOSUM.

Matrices PAM: Margaret Dayhoff fue la primera en desarrollar la matriz PAM, PAM significa Point Accepted Mutations. Las matrices PAM se calculan observando las diferencias en proteínas estrechamente relacionadas. Una unidad PAM (PAM1) especifica una mutación puntual aceptada por cada 100 residuos de aminoácidos, es decir, 1% de cambio y 99% permanece como tal.

BLOSUM: La matriz de sustitución de bloques, desarrollada por Henikoff y Henikoff en 1992, utilizó regiones conservadas. Estas matrices son valores de identidad porcentuales reales. Para decirlo simplemente, dependen de la similitud. Blosum 62 significa que hay un 62% de similitud.

Puntaje de brecha o penalización por brecha: Los algoritmos de programación dinámica utilizan penalizaciones por huecos para maximizar el significado biológico. La penalización por espacio se resta por cada espacio que se haya introducido. Existen diferentes penalizaciones por brecha, como apertura de brecha y extensión de brecha. La puntuación de la brecha define una penalización otorgada a la alineación cuando tenemos inserción o eliminación. Durante la evolución, puede haber un caso en el que podamos ver espacios continuos a lo largo de la secuencia, por lo que la penalización del espacio lineal no sería apropiada para la alineación. Por lo tanto, se ha introducido la apertura y la extensión de la brecha cuando hay brechas continuas (cinco o más). La penalización de apertura siempre se aplica al comienzo de la brecha, y luego las otras brechas siguientes se otorgan con una penalización de extensión de brecha que será menor en comparación con la penalización de apertura. Los valores típicos son –12 para la apertura de la brecha y –4 para la extensión de la brecha.


Introducción

Hoy en día, el concepto de red de Internet de las cosas (IoT) se ha convertido en una parte integral de la infraestructura de información moderna de la sociedad. IoT es una red única que conecta los objetos inteligentes del mundo real y los objetos virtuales que nos rodean. El número y la variabilidad de estos objetos (dispositivos inteligentes) sigue aumentando, lo que afecta a diversos aspectos de la vida humana, desde los vehículos hasta la electrónica móvil y la asistencia sanitaria [26]. In other words, the IoT is not just a set of different devices and sensors connected by wired and wireless communications and the global cyber space of the Internet, but it is a closer integration of the real and virtual worlds, in which communication takes place between people and devices.

The sustainability of IoT is the availability of the system to perform its functions in the context of external influence [6]. Considering that the subsystems and components of the IoT have many horizontal connections, thus forming a heterogeneous cyber infrastructure with a large number of entities, most of which lack built-in protection mechanisms the problem of network security in such networks is especially actual. Main attack vectors are aimed for overtaking the control by the IoT device and capturing the confidential data, as well as the purposeful node deactivation [1]. Not only objects of the virtual world�ta, files, personal information𠅊re under threat, but also physical objects of the real world. According to a report by Kaspersky Laboratory, in the first half of 2019, more than 100 million attacks were detected on the smart IoT devices, which are seven times more than in the <"type":"entrez-nucleotide","attrs":<"text":"H12018","term_id":"876838","term_text":"H12018">> H12018 [10]. Network infrastructure and wireless data transmission channels are the most vulnerable objects of the modern infocommunication environment [27]. Attackers using wireless links can remotely invade a target subnet or device (group of devices), intercept traffic, launch denial of service attacks (including distributed attacks), and take control of the IoT devices to create megabotnets.

In 2020, the world is facing with the COVID-2019 coronavirus pandemic, and life has almost completely moved to the network, people around the world work, study, shop and have fun online. This could not affect the goals of the cybercriminals, medical organizations, educational services, delivery, etc., faced massive DDoS attacks. A large network of hospitals in France fell victim to one of these attacks, when attackers tried to disable the infrastructure of medical institutions. As a result of the attack, hospital staff working remotely was unable to use work programs and corporate e-mail for some time. In Germany, on the first day of distance learning, a distance learning platform was attacked. The service through which teachers exchange teaching materials, homework, and tests with students was not available. In the Netherlands, the food delivery service Thuisbezorgd was unable to process orders as a result of a DDoS attack and had to refund customers. In the first quarter of 2020, there was a significant increase in the number and quality of DDoS attacks. In particular, the popularity of smart attacks that exploit vulnerabilities in the network infrastructure is noted. SYN flood is the leader among the types of attacks (92.6%) the share of attacks via ICMP continued to grow and exceeded the share of UDP and TCP floods (Kaspersky [11].

To counter cyber attacks at the IoT, as in traditional networks, various intrusion detection systems (IDS) are applied (e.g., [17]. There are two main approaches on which most the IoT IDSs are based: anomaly detection and misuse detection. The advantages of the former are a global view on the network, the ability to detect new attacks, and the use of fewer rules (compared to signature methods) their disadvantages include a high level of errors of the first and second kind and low adaptation for changing conditions (new profiles, dynamic anomalies). The advantages of an IDS based on search for abuse are reliability, speed, low false positives for known intrusions. Its disadvantages are the strict dependence on the relevance of the signature base and the impossibility of detecting new attacks.

The work of an IDS usually consists of three stages: (1) monitoring, (2) sequence extraction and misuse detection by pattern matching, (3) signaling of attack to provide the attack response. Matching with attack patterns is currently the main method for IDS when detecting malicious activity [13] however, it has two significant drawbacks. Firstly, the IoT-specific attacks, such as forced power consumption, forced topology change, etc., have a split sequence of operations, time intervals in the chain of actions, and some attacks may also have a non-linear sequence of actions. Secondly, there is a class of polymorphic attacks that have mutations (namely local differences, omissions, delays) in the sequences of actions during the implementation of the attack. These polymorphic attacks adapt to a wide range of conditions, operating systems, and circumstances and try to avoid scanning by defenses to infect endpoints [8]. They are called the polymorphic attacks because they have different signatures that make them difficult to identify using a single signature. For example, in order to disguise ongoing network attacks, attackers can use polymorphic shellcode to create unique attack patterns. This method usually involves encoding the payload, with the decoder placed at the front of the payload before sending it. All known the pattern matching methods do not detect such variations of a single sample.

Our research proposes new, the nature inspired, technologies, namely a genetic sequence alignment computing and a sequence similarity calculation, instead of massive equity checking of multiple packets and signatures traditionally used for the IDS composing. The aim of our research is to assess the prospects of using the biological coded sequence alignment algorithms for solving the task of detection the specific network intrusions. The novelty of our results is the fact that it has been proposed to encode network packets (or the chain of activity acts) into the sequences of the nucleotide codes for their subsequent alignment and matching with patterns. The matching operation is based on the similarity checking, not equity checking, as it was usually applied for the intrusion detection. Therefore, our contribution to the cyber security is the proposed bio-inspired approach that, in contrast to traditional methods, makes it possible to detect new variations of the attacks in the IoT networks, to reduce the signature database, and to increase the detection effectiveness on the low-resource devices.

The following material is organized in the next manner: Sect.ਂ reviews successful cases of applying modern nature-inspired methods in solving cyber security issues Sect.ਃ discusses methods for aligning sequences: global, local, and additive approaches Sect.਄ presents the proposed coding and alignment technique Sect.ਅ presents our results of the experiments on detecting the DDoS attacks using a BoT-IoT dataset on the portative IoT Raspberry Pi4 platform Sect.ਆ presents a discussion of the results of applying the bio-inspired methods Sect.ਇ concludes our contribution.


Fondo

Biological sequence alignment is a cornerstone of bioinformatics and is widely used in such fields as phylogenetic reconstruction, gene finding, genome assembly. The accuracy of the sequence alignments and similarity measures are directly related to the accuracy of subsequent analysis. CDS alignment methods have many important applications for gene tree and protein tree reconstruction. In fact, they are useful to cluster homologous CDS into groups of orthologous splicing isoforms [1, 2] and combine partial trees on orthology groups into a complete protein tree for a gene family [3, 4]. Aligning and measuring the similarity between homologous CDS requires to account for frameshift (FS) translations that cannot be detected at the amino acid (AA) level, but lead to a high similarity at the nucleotide level between functionnaly different sub-sequences.

FS translation consists in alternative AA translations of a coding region of DNA using different translation frames [5]. It is an important phenomenon resulting from different scenarios such as, insertion or deletion of a nucleotide sequence whose length is not a multiple of 3 in a CDS through alternative splicing [6, 7] or evolutionary genomic indels [8, 9], programmed ribosomal frameshifting [10], or sequencing errors [11]. Recent studies have reported the role of FS translations in the appearance of novel CDS and functions in gene evolution [6, 12]. FS translation has also been found to be linked to several diseases such as the Crohn’s disease [13]. The computational detection of FS translations requires the alignment of CDS while accounting for their codon structure. A classical approach for aligning two CDS used in most alignment tools [14, 15] consists in a three-step method, where the CDS are first translated into AA sequences using their actual coding frame, then AA sequences are aligned, and finally the AA alignment is back-translated to a CDS alignment. This approach does not account for alternative AA translations between two CDS and it leads to incorrect alignment of the coding regions subject to FS translation. The opposite problem of aligning protein sequences while recovering their hypothetical nucleotide CDS sequences and accounting for FS translation was also studied in several papers [16, 17].

Here, we consider the problem of aligning two CDS while accounting for FS translation, by simultaneously accounting for their nucleotide and AA sequences. The problem has recently regained attention due to the increasing evidence for alternative protein production through FS translation by eukaryotic gene families [18, 19].

The problem was first addressed by Hein et al. [20, 21] who proposed a DNA/protein model such that the score of an alignment between two CDS of length norte y metro is a combination of its score at the nucleotide level and its score at the AA level. They described a O(norte 2 metro 2 ) algorithm in [20], later improved to a O(nm) algorithm in [21] for computing an optimal score alignment, under the constraint that the search space of the problem is restricted. Arvestad [22] later proposed a CDS alignment scoring model with a O(nm) alignment algorithm accounting for codon structures and FS translations based on the concept of generalized substitutions introduced in [23]. In this model, the score of a CDS alignment depends on its decomposition into a concatenation of codon fragment alignments, such that a codon fragment of a CDS is defined as a substring of length w, (0le w le 5) . This decomposition into codon fragment alignments allows to define a score of the CDS alignment at the AA level. More recently, Ranwez et al. [18] proposed a simplification of the model of Arvestad limiting the maximum length of a codon fragment to 3. Under this model, a O(nm) CDS alignment algorithm was described and extended in the context of multiple sequence alignment [18]. In the models of Arvestad [22] and Ranwez et al. [18], several scores may be computed for the same alignment based on different decompositions into codon fragment alignments. The corresponding algorithms for aligning two CDS then consist in computing an optimal score decomposition of an alignment between the two CDS. This optimal score exclusively accounts for FS translation initiations, i.e a FS translation in an alignment is penalized by adding a constant FS cost, which only penalizes the initiation of the FS, not accounting for the length of this FS translation. However, taking account of FS translation lengths is important in order to increase the precision of CDS alignment scores, as these lengths induce more or less disruptions between the protein sequences.

In this paper, we propose the first alignment algorithm that accounts for both the initiation and the length of FS translations in order to compute the similarity scores of CDS alignments. The remaining of the paper is organized as follows. In the “Motivation”, we illustrate the importance of accounting for FS translation length when aligning CDS. In the “Preliminaries”, we give some preliminary definitions and we introduce a new CDS alignment scoring model with a self-contained definition of the score of an alignment penalizing both the initiation and the extension of FS translations. In the “Methods”, a dynamic programming algorithm for computing an optimal score alignment between two CDS is described. Finally, in the “Results”, we present and discuss the results of a comparison of our method with other CDS alignment methods for a pairwise comparison of CDS from homologous genes of ten mammalian gene families.

Motivation: importance of accounting for FS translation length

The two main goals of aligning biological sequences are to evaluate the similarity and to identify similar regions between the sequences, used thereafter to realize molecular analyses such as evolutionary, functional and structural predictions. In practice, CDS alignment can be used to exhaustively identify the conserved features of a set of proteins. Thus, the definition of CDS similarity must account for sequence conservation and disruptions at both the nucleotide and the protein levels.

Figure 1 illustrates the importance of accounting for AA translations and FS translation length in order to compute an adequate similarity score for a CDS alignment. It describes an example of three CDS Seq1 , Seq2 and Seq3 . Seq1 has a length of 45. The CDS Seq2 has length 60 and is obtained from Seq1 by deleting the nucleotide ‘G’ at position 30 and adding 16 nucleotides at the end. The CDS Seq3 has length 60 and is obtained from Seq1 by deleting the nucleotide ‘G’ at position 15 and adding 16 nucleotides at the end.

Cima an example of three CDS Seq1 , Seq2 and Seq3 . Middle an optimal alignment between Seq1 and Seq2 with a FS translation region of length 15. Fondo an optimal alignment between Seq1 and Seq3 with a FS translation region of length 30

When looking at the AA translations of Seq1 , Seq2 and Seq3 , we observe that the similarity between Seq2 and Seq1 is higher than the similarity between Seq3 and Seq1 at the protein level, because Seq1 and Seq2 share a longer AA prefix “M T E S K Q P W H” (amino acids in black characters in the alignments). However, the pairwise CDS alignment algorithms that do not account for the length of FS translations would return the same score for the two following optimal alignments of Seq1 with Seq2 and Seq1 with Seq3 , penalizing only the initiation of one FS translation in both cases (positions marked with a “!” symbol in the alignments), and not penalizing the sequence disruptions at the protein level.

From an evolutionary point of view, a good scoring model for evaluating the similarity between two CDS in the presence of FS translations should then penalize not only the initiation of FS but also the length of FS translations extension (amino acids in gray characters in the alignments). The alignment of Seq1 with Seq2 would then have a higher similarity score than the alignment of Seq1 with Seq3 .

Preliminaries: score of CDS alignment

In this section, we formally describe a new definition of the score of a CDS alignment that penalizes both the initiation and the extension of FS translations.

Definición 1

[Coding DNA sequence (CDS)] A coding DNA sequence (CDS) is a DNA sequence on the alphabet of nucleotides (Sigma _N=) whose length norte is a multiple of 3. A coding sequence is composed of a concatenation of (frac<3>) codons that are the words of length 3 in the sequence ending at positions 3I, (1 le i le frac<3>) . The AA translation of a CDS is a protein sequence of length (frac<3>) on the alphabet (Sigma _A) of AA such that each codon of the CDS is translated into an AA symbol in the protein sequence.

Note that, in practice an entire CDS begins with a start codon “ATG” and ends with a stop codon “TAA” , “TAG” or “TGA” .

Definición 2

(Alignment between DNA sequences) An alignment between two DNA sequences A y B is a pair ((A',B')) where (A') and (B') are two sequences of same length L derived by inserting gap symbols ('-') in A y B, such that (forall i,

1 le i le L) , in the alignment is called a column of the alignment.

Given an alignment ((A',B')) of length L between two CDS A y B, let S be the sequence (A') or (B') . We denote by (S[k

1 le k le l le L) , the substring of S going from position k to position l. (left| ight|) denotes the number of letters in () that are different from the gap symbol ('-') . For example, if (A'= exttt) and (B'= exttt) , (|A'[4

8]| = | exttt| = 3) . A codon of A o B es grouped in the alignment ((A',B')) if its three nucleotides appear in three consecutive columns of the alignment. For example, the first codon ACC of A is grouped, while the first codon ACT of B is not grouped.

An alignment ((A',B')) of length 48 between two CDS, A (13 codons) and B (14 codons). los number arrays indicate the positions of the consecutive alignment columns. Codons of A y B están colored according to the set to which they belong: IM codons in blue color, FSext codons in red color, InDel codons in green color and FSinit codons in black color. MFS nucleotides contained in FSinit codons are underlined

In the following, we give our definition of the score of an alignment ((A',B')) between two CDS A y B. It is based on a partition of the codons of A (resp. B) into four sets depending on the alignment of codons (see Fig. 2 for an illustration):

The set of In-frame Matching codons (IM) contains the codons that are grouped in the alignment and aligned with a codon of the other CDS.

The set of Frameshift extension codons (FSext) contains the codons that are grouped in the alignment and aligned with a concatenation of three nucleotides that overlaps two codons of the other CDS.

The set of Deleted/Inserted codons (InDel) contains the codons that are grouped in the alignment and aligned with a concatenation of 3 gap symbols.

All other codons constitutes Frameshift initiation codons (FSinit) . The set of Matching nucleotides in FSinit codons (MFS) contains all the nucleotides belonging to FSinit codons and aligned with a nucleotide of the other CDS.

The following notations and conventions are used in Definition 3 to denote the different sets of codons and nucleotides in A y B. The set of IM codons in A (resp. B) is denoted by ( exttt_) (resp. ( exttt_) ). The set of FSext codons in A (resp. B) is denoted by ( exttt_) (resp. ( exttt_) ). The set of InDel codons in A (resp. B) is denoted by ( exttt_) (resp. ( exttt_) ). The set of MFS nucleotides in A (resp. B) is denoted by ( exttt_) (resp. ( exttt_) ). In these sets, the codons of A y B are simply identified by the position (column) of their last nucleotide in the alignment. In this case, we always have ( exttt_ = exttt_) as in the example below. The MFS nucleotides are also identified by their positions in the alignment.

In the alignment scoring model described in Definition 3, the substitutions of IM and FSext codons are scored using an AA scoring function (s_) such that aligned codons with silent nucleotide mutations get the same score as identity. A fixed FS extension cost denoted by fs_extend_cost is added for each FSext codon. The insertions/deletions of InDel codons are scored by adding a fixed gap cost denoted by gap_cost for each InDel codon. The alignment of MFS nucleotides are scored independently from each other, using a nucleotide scoring function (s_). The insertions or deletions of nucleotides in FSinit codons are responsible for the initiation of FS translations. They are then scored by adding a fixed FS opening cost denoted by fs_open_cost for each FSinit codon. Note that, by convention, the values of all penalty costs for gap and FS ( gap_cost , fs_open_cost , fs_extend_cost ) are negative. Note also that the scoring scheme assumes that the AA and the nucleotide scoring functions, (s_) and (s_) , are symmetric.

Definition 3

(Score of an alignment) Let ((A',B')) be an alignment of length L between two CDS A y B. The score of the alignment ((A',B')) is defined by:


Title: Pocket arithmetic and Needleman-Wunsch on Cray Research computers

In the interest of providing more efficient computer-based analysis of DNA and protein sequences, Cray Research has developed a high performance implementation of the sequence alignment method of Needleman and Wunsch using the programming technique of pocket arithmetic. The basis for this implementation is the program SEQHDP, which finds locally homologous subsequences of a protein sequence pair and determines the statistical significance of the homology. Pocket arithmetic takes advantage of the 64-bit width of an operand on the Cray Y-MP by packing more than one integer value per word, then performing logical or integer operations on the packed word to yield multiple results per operation. This technique, in combination with the vector processing capabilities of the Cray Y-MP CPU, produces substantially improved performance over the conventionally coded version of the same algorithm. The authors will introduce the programming technique of pocket arithmetic, then describe its implementation in the Needleman-Wunsch sequence comparison function in SEQHDP. Performance results based on actual protein sequence comparisons are presented.


Ver el vídeo: T6 BBCyG2021 Alix2 (Agosto 2022).