Metodo blast.

Resumen

BLAST

La búsqueda de secuencias biológicas es ampliamente utilizada en el campo de la bioinformática y la biología computacional para determinar la similitud entre las secuencias biológicas .Muchos métodos computacionales se han sugerido para la alineación de secuencias. Por ejemplo, la programación dinámica proporciona una solución para alinear las búsquedas de secuencias biológicas con tiempo de complejidad del orden de O (MN). Enfoque heurístico siempre funciona para encontrar las secuencias relacionadas en una búsqueda de base de datos pero no tiene la garantía de una solución óptima al igual que el algoritmo de programación dinámica, pero estos métodos son 50-100 veces más rápido que la programación dinámica, por lo tanto mejor adecuado para bases de datos de búsqueda. En este trabajo un estudio de diversos métodos de cálculo utilizados para alinear las biológicas secuencias se han dado para diferentes datos auxiliares estructura para secuencias de lectura o secuencias de referencia o ambos. Palabras clave - El alineamiento de secuencias, programación dinámica, enfoque heurístico, estructura de datos auxiliar.

Introducción

La búsqueda de secuencia de datos es una de las principales tareas en el bioinformática Consiste en alinear una secuencia de consulta a una base de datos de secuencia con el objetivo de determinar las secuencias de datos que tienen coincidencias estadísticamente significativos en la secuencia de consulta. Es diferente del clásico problema de la coincidencia de cadenas en informática, donde estamos interesados ​​en saber coincidencias exactas. La secuencia de alineación de datos es un problema de la coincidencia de cadenas aproximadas a las coincidencias de cadenas que permiten errores. El problema en su mayor parte de forma general es encontrar la posición de un texto en el que un determinado patrón ocurre lo que permite un número limitado de errores en el partido. Los errores son aquellas operaciones que el biólogo sabe son comunes a ocurrir en las secuencias genéticas. La distancia entre las dos secuencias se define como la Secuencia mínima de operaciones para transformar una en la Otra. Con respecto a la probabilidad, las operaciones son asignadas a un coste, de manera que las operaciones más probables son más baratos y el objetivo es reducir al mínimo el coste total.

Desarrollo

A. Alineación de Secuencia

Un alineamiento entre dos secuencias es simplemente un partido por parejas entre los caracteres de cada secuencia. Una verdadera alineación de nucleótidos o de aminoácidos Las secuencias de ácido es aquella que refleja la relación entre dos o más secuencias homólogas que comparten un ancestro en común. Si es el mismo en ambas secuencias a continuación, esta posición se ha conservado en la evolución. Si las letras difieren se asume que los dos se derivan de una secuencia ancestral.

(Que podría ser uno de los dos o ninguno). Las secuencias homólogas pueden tener longitud diferente, sin embargo, casi explica a través de inserciones o de elecciones en las secuencias. Por lo tanto, una letra o un tramo de letras pueden ser emparejados con guiones en la otra secuencia para significar una inserción o selección. Ya que una inserción en una secuencia siempre puede ser vista como una selección en el otro se utiliza con frecuencia el término " Indel”.

[pic 1]

Tres posibles alineamientos con guiones entre dos secuencias cortas.

La secuencia de alineación se puede dividir principalmente en dos categorías:

1) Secuencia par de alineaciones

 El análisis por parejas de secuencia examina las similitudes de dos secuencias mediante la búsqueda de la alineación con la puntuación más alta. Hay dos tipos de alineaciones para análisis de la secuencia de pares basado en programación dinámica Método:

1. la alineación global: Intentar alinear cada residuo en cada secuencia, son más útiles cuando la secuencias en el conjunto de consultas son similares y aproximadamente el mismo tamaño Needleman y Wunsch fueron los primeros en presentar una programación dinámica un algoritmo que podía encontrar la alineación global entre dos secuencias de aminoácidos.

1. la alineación local: son más útiles para similares secuencias que se sospecha que tienen regiones de similitud de secuencia dentro de su contexto más amplio. Smith y Waterman introdujeron un nuevo algoritmo con un método diferente de puntuación y similitud con el objetivo de encontrar óptimo local de sub-secuencias de alineación, a expensas de la puntuación global.

B. alineación de secuencias múltiples

Alineación de secuencias múltiples tiene como objetivo encontrar similitudes entre muchas secuencias. Una de las secuencias múltiples soluciones de alineación son algoritmos heurísticos con enfoques aproximados, tales como la familia de CLUSTAL

Programas creados por Higgins que utilizan una progresiva algoritmo de Feng y Doolittle. Perfil oculto Modelos de Markov (HMM) proporcionan otra exitosa solución al problema de MSA. Fueron introducidos por Krogh y sus colegas en 1994. Un conjunto de métodos para producir MSA y el tiempo que reduce los errores inherentes y a los métodos progresivos que son clasificados como "iterativos" porque que funcionan de manera similar a los métodos progresivos pero repetidamente realinean las secuencias iniciales, así como la adición de nuevos secuencias a la creciente MSA. Basado en iteraciones populares método llamado muscular (por alineación de secuencias múltiples log-expectativa) mejora en los métodos progresivos con una medida de la distancia más precisa para evaluar la relación de dos secuencias. Tanto par de secuencias sabias y múltiples algoritmos de adaptación utilizan matrices de sustitución para anotar en la alineación de secuencias. Sustitución de las matrices evalúan posibles sustitutos de proteínas y secuencias de ácidos nucleicos. Tanto la alineación de secuencias de pares y algoritmos múltiples utilizan matrices de sustitución para anotar la secuencia de alineación. En sustitución de las matrices de cada posible residuo sustituciones que dan una puntuación que refleja la probabilidad de tal cambio. Hay dos proteínas de sustitución popular de los modelos de matrices: Porcentaje Aceptado de Mutación (PAM) y Bloques de sustitución de matriz (BLOSUM) En este artículo se revisan las técnicas de alineación generales, sus mejoras, aplicaciones y sus deficiencias Por último vamos a discutir el futuro de los algoritmos de alineación.

II. DESCRIPCIÓN GENERAL DE LA ALINEACIÓN DE SECUENCIA

ALGORITMOS

Needleman - Wunsch es un algoritmo bien knoxm para el mundial alineación basada en el concepto de programación dinámica pero es adecuada para secuencias cortas y se vuelve muy reducir la velocidad en caso de secuencias largas (La hora de la complejidad algoritmo de Needleman Wunsch es O (MN)). Herrero- Waterman algoritmo hace la alineación local y compara todos bases contra de todas las bases que es claramente demasiado lento su tiempo complejidad es el mismo que para Needleman - Wunsch algoritmo Una solución de este enfoque se da por BLAST1151 que encontrar semillas partidos cortos exactas que después los correspondientes al ya la alineación

A. FASTA y BLAST la Familia FASTA y BLAST

 ambos son métodos heurísticos de podar el espacio de búsqueda mediante el uso de métodos aproximados rápidos para seleccionar las secuencias de la base de datos que es probable que sean  similares a la consulta y para localizar la región de similitud dentro de ellos. El algoritmo FASTA realiza optimización local de porciones de modo que difieren de la secuencia fuera de la región de la alineación optimizada no afectan a la puntuación de la alineación. Para refinar la búsqueda se utiliza el algoritmo FASTA la tabla de búsqueda es más rápida para localizar todas las identidades o grupos de identidades entre dos secuencias de ADN o de aminoácidos para la primera etapa de comparación. En conjunción con la tabla de búsqueda que utiliza el método diagonal para encontrar todas las regiones de similitud entre las dos secuencias. La velocidad y la sensibilidad es controlado por el parámetro llamado ktup (k touple) que especifica el tamaño de la palabra. Menor el valor ktup más sensible es la búsqueda por ktup por defecto = 2 es para la búsqueda Proteina y 4 o 6 es por de nucleótidos. Este método identifica región de una diagonal que tiene la mayor densidad de partidos ktup. FASTA utiliza una fórmula para anotando partidos ktup que incorporan el pam real 250 valores de residuos alineados. FASTA ahorra algo mejor locales regiones, independientemente de si existen o no en la misma o en diferentes diagonales. Estas pocas regiones de alta puntuación son alineaciones parciales sin lagunas. Entonces algoritmo FASTA comprueba que si hay varias regiones iniciales con puntaje mayor que el punto de corte se comprueba si se pueden unir para obtener un alineamiento con huecos.

...