El mapeo de lecturas cortas ( en inglés Short-Read Sequence Alignment, Short-Read Sequence Mapping ) es un método bioinformático para analizar los resultados de la secuenciación de segunda generación , que consiste en determinar posiciones en el genoma o transcriptoma de referencia, de donde podría extraerse cada lectura corta específica. obtenerse con la mayor probabilidad. Suele ser el primer paso en el procesamiento de datos si se conoce el genoma del organismo en estudio.
Las plataformas de secuenciación de próxima generación permiten la secuenciación eficiente de millones de secuencias cortas de 50-500 pb. Para hacer esto, la molécula de ADN o ADNc se divide en muchos segmentos cortos, que luego se secuencian en paralelo. Después de obtener las secuencias secuenciadas de estos segmentos cortos (lecturas), se debe reconstruir el genoma completo o el conjunto de secuencias de ADNc a partir de ellas. Para ello, es necesario determinar para cada lectura la posición más probable en el genoma de referencia.
A diferencia del reensamblaje de novo , que reúne lecturas para reconstruir este genoma desconocido, muchos proyectos actuales tienen un "genoma de referencia", un genoma cercano ya conocido de otro organismo. O podría ser un conjunto de secuencias de referencia. En este caso, para dar algún significado a la lectura, se debe determinar su posición en los datos de referencia. Este proceso se llama mapeo o alineación . El mapeo puede tener una apariencia ligeramente diferente para diferentes tareas, por ejemplo: para el mapeo genómico, los espacios grandes deben estar ausentes, mientras que para RNA-seq están permitidos debido a la presencia de empalmes. En general, las tareas de asignación no han cambiado desde la última generación de secuenciadores, pero los programas desarrollados para la generación anterior no están diseñados para funcionar con mayores volúmenes de datos y tampoco funcionan bien con lecturas de corta duración.
El principal problema es que el genoma estudiado difiere del genoma de referencia debido a la variabilidad del genoma (por ejemplo, debido a SNPs o indels), así como debido a errores de secuenciación. Debido a esto, la alineación de una lectura y su posición "correcta" en el genoma de referencia puede ser más diferente que la alineación de esta región con cualquier otra ubicación en el genoma de referencia, por lo que los programas de mapeo deben poder encontrar coincidencias inexactas. Para ello se utilizan varias heurísticas. Cuando se superpone a esto la posibilidad de empalme en el caso de RNA-seq, el problema se vuelve aún más complicado.
Las lecturas pertenecientes a elementos repetitivos también son un problema. En este caso, no siempre es posible decidir inequívocamente dónde mapear esta lectura. Tal secuencia puede mapearse aleatoriamente en cualquier sitio adecuado, o etiquetarse como mapeada en múltiples sitios.
Si el genoma de referencia es grande y se han realizado miles de millones de lecturas, el tiempo de mapeo es un problema importante. La alineación siempre ha sido una tarea que requiere muchos recursos, pero en este caso el problema alcanza un nivel cualitativamente nuevo, que requiere una racionalidad extraordinaria y un uso eficiente del tiempo del procesador y la memoria de los algoritmos.
Hay dos enfoques principales para resolver estos problemas: usar tablas hash y usar árboles o matrices de sufijos.
El proceso de búsqueda mediante hashing es muchas veces más rápido y menos costoso que la alineación clásica mediante programación dinámica para el algoritmo de Smith-Waterman .
Este enfoque usa una función hash que le permite transformar una cadena en una clave que se puede usar para búsquedas rápidas. La forma más sencilla sería dividir el genoma en palabras que coincidan con la longitud de la lectura, pero este enfoque no funciona, ya que es más probable que las palabras largas sean únicas y su almacenamiento ocuparía demasiado espacio en la memoria. En su lugar, se utiliza el hashing de secciones más cortas, que son mucho más comunes. Después de que la función hash haya obtenido las posiciones adecuadas, se puede intentar asignar el resto de la lectura al genoma. Además, el enfoque de dividir la lectura en varias partes le permite incluir la posibilidad de sustituciones en el algoritmo. Entonces, en el programa Maq, la lectura se divide en 4 partes, llamadas semillas (secciones cortas con coincidencias exactas). Si la lectura encaja perfectamente con la referencia, entonces las 4 semillas encajan perfectamente. Si hay una discrepancia en la lectura, que probablemente se deba a la presencia de SNP o errores de secuenciación, entonces caerá en una de las semillas, mientras que las otras 3 aún se mapearán perfectamente. Asimismo, con dos reemplazos, al menos dos semillas se mapearán perfectamente. Por lo tanto, al mapear todos los pares posibles de lecturas usando la indexación (habrá 6 de ellos, ya que las semillas deben ir en cierto orden), obtendremos un conjunto limitado de lugares en el genoma donde se puede mapear la lectura completa, después de el cual es posible utilizar la alineación habitual para determinar cuál de las posiciones encaja mejor (ver imagen 1a). SOAP, RMAP y SeqMap funcionan de manera similar.
Una modificación de este enfoque puede ser la idea de considerar todas las k-medidas de lectura, en lugar de secciones no superpuestas de cierta longitud. Entonces, para leer ACGT, habrá 3 de ellos: AC, CG, GT. SHRiMP2 y RazerS funcionan de manera similar. Esto aumentará la sensibilidad, pero también aumentará el costo del tiempo.
Toda esta información ocupa mucho espacio en la memoria. Para reducir la cantidad de memoria consumida, la mayoría de los programas usan codificación de nucleótidos de dos bits (A 00, C 01, G 10, T 11), pero esto no permite usar el nucleótido ambiguo N, que puede estar presente tanto en lecturas como en lecturas. en el genoma de referencia. Los programas toman diferentes enfoques para evitar esto. Entonces BWA reemplaza N con un nucleótido aleatorio, y SOAP2 reemplaza todo N con G.
Se pueden utilizar varias mejoras para acelerar los algoritmos y solucionar los errores. Por ejemplo, use posiciones indiferentes (denotemoslas con una X). Entonces, la semilla ACGxACG se alineará tanto en ACGAACG como en ACGCACG, lo que aumenta la sensibilidad del mapeo (aunque aumenta el tiempo de procesamiento, ya que habrá más hallazgos para cada lectura). Esto se usa en programas como Zoom, BFAST, GASSST, SHRiMP2, PerM.
La mayor parte del tiempo, los algoritmos no se dedican a buscar semillas, sino a comprobar su entorno. La mayoría de los programas utilizan el algoritmo de Needleman-Wunsch o sus modificaciones. Otros, como GASSST, agregan un paso intermedio de medición de la distancia de Euler, que simplemente tiene en cuenta el número de letras idénticas. Por ejemplo, si estamos tratando de mapear una lectura que contiene 5 G a una región que contiene solo 1 G, entonces tendremos al menos 4 reemplazos. Este enfoque le permite eliminar rápidamente áreas inadecuadas y aplicar enfoques más precisos (pero también costosos) solo a regiones prometedoras.
Es posible no codificar el genoma y buscar lecturas en él, sino codificar las lecturas y buscar secciones del genoma de la misma longitud en ellas. Las primeras versiones de Maq, Rmap y SeqMap usaban este enfoque, pero desde entonces la cantidad de lecturas en un experimento ha aumentado considerablemente y este enfoque ha dejado de ser racional.
Los algoritmos basados en hashing no se adaptan bien a las repeticiones, ya que el número de semillas que deben comprobarse aumenta considerablemente. Para resolver esto se utilizan algoritmos basados en árboles de sufijos y matrices de sufijos . La ventaja de este enfoque, en particular, es que las repeticiones no aumentan el tiempo de ejecución del algoritmo, ya que las secciones repetidas "colapsan" en el árbol de sufijos. En su forma más pura, este enfoque funcionará extremadamente rápido, siempre que no haya errores ni sustituciones (por ejemplo, lo utiliza el programa MPscan).
La matriz de sufijos se utiliza para ahorrar más memoria. En general, buscar a través de una matriz de sufijos no es fundamentalmente diferente de trabajar con un árbol de sufijos, pero requiere un enfoque un poco más complejo. A menudo se utiliza la transformación de Burroughs-Wheeler . Después de todas las transformaciones, el tamaño de dicha matriz de sufijos es comparable al tamaño del genoma original. Entonces, para todo el genoma humano, la matriz de sufijos creada por el programa Bowtie ocupa 2 gigabytes. En comparación, una base de datos de índices basados en hash (como la que se usa en el programa Maq) ocupa alrededor de 50 gigabytes de memoria.
El algoritmo de Ferragin-Manizi se utiliza para buscar palabras .
De forma simplificada, el proceso es el siguiente. Las lecturas alinean un nucleótido con el genoma transformado por Burrows-Wheeler. Cada nucleótido alineado permite que el programa reduzca el número de lugares donde puede ir la lectura completa. Si el programa no encuentra una posición en la que la lectura encaje perfectamente, vuelve al paso anterior, realiza un reemplazo y continúa la búsqueda. Así es como funciona, por ejemplo, SHRiMP. Por otro lado, si la cantidad de errores permitidos es grande, esto comienza a ralentizar el algoritmo. Se usa una modificación un poco más interesante en el programa BWA: primero alinea las partes izquierda y derecha de la lectura, suponiendo que al menos una de estas dos regiones tendrá menos errores (que se basa en el hecho de que el extremo 5' es generalmente mejor secuenciado).
Por el momento, hay programas que utilizan tanto uno como el otro enfoque. A pesar de que los programas basados en la transformación de Burroughs-Wheeler son ahora más populares, no se puede decir que este enfoque sea mejor. Estos programas son más rápidos y mejores para manejar repeticiones que los programas basados en hash, pero es menos probable que manejen errores. La situación opuesta se observa para el segundo tipo de programas: el hash te permite contabilizar bien los errores, pero empieza a consumir mucho tiempo al encontrar repeticiones.
En este caso, la posibilidad de empalme debe ser incluida en la consideración. Básicamente, se utiliza el conocimiento sobre exones e intrones ya conocidos, lo que permite crear una base de datos formada por asociaciones exón-exón, y ya sobre ella implementar algoritmos convencionales, como bowtie o maq. Obviamente, este enfoque no tiene en cuenta los intrones previamente desconocidos, por lo que se puede combinar con el aprendizaje automático para predecir empalmes desconocidos.
Otro enfoque podría no usar la anotación en absoluto. En el modo de operación sin anotación, TopHat primero determina los exones potenciales, crea una base de datos de sitios de empalme potenciales en función de esta información y luego mapea las lecturas usándola. Los exones potenciales están determinados por las ubicaciones de las lecturas de RNA-seq adyacentes cuando se alinean con el genoma. Debido a que muchos exones son más cortos que los generados por los secuenciadores de lectura actuales, no se detectarán durante la fase de mapeo inicial. TopHat resuelve este problema principalmente dividiendo las lecturas en fragmentos más cortos y mapeándolos de forma independiente.
TopHat utiliza dos métodos principales para identificar posibles sitios de empalme. El primer y principal factor a favor de un sitio potencial de empalme es cuando dos segmentos de una lectura (para lecturas de 45 pares de bases o más de longitud) se asignan a una cierta distancia entre sí o cuando el segmento interno de la lectura no se puede mapeado Otro factor es la aparición de pares de "islas de cobertura", que son lugares donde muchas lecturas de RNA-seq se mapean una al lado de la otra. Las islas vecinas a menudo se cortan juntas y están una al lado de la otra en la transcripción, por lo que TopHat está buscando formas de conectarlas mediante un intrón.
El principal problema con los algoritmos basados en anotaciones es que dependen en gran medida de la calidad de las anotaciones en sí, mientras que los algoritmos que utilizan el aprendizaje automático dependen en gran medida de la calidad del conjunto de entrenamiento. Además, dado que las nuevas anotaciones se basan en las antiguas, los errores en las anotaciones pueden "propagarse", haciéndose cada vez más "significativos" y mucho más difíciles de detectar.
Abreviatura del inglés. Herramienta de búsqueda rápida y precisa similar a Blat . Los desarrolladores del programa se han centrado en la sensibilidad del programa a errores, SNP e indels, lo que le permite elegir un equilibrio entre velocidad y precisión.
Admite la secuenciación de extremos emparejados . Utiliza el algoritmo de Smith-Waterman para la alineación final con soporte para espacios y la definición de pequeños indeles [1] . Capaz de trabajar en modo paralelo en un clúster. Existe una versión del programa bfast+bwa. Admite formatos de datos Illumina, ABI SOLiD, 454, Helicos.
Herramienta de alineación tipo BLAST. Optimizado para la velocidad mediante el uso de un índice de fragmentos K no superpuestos que cabe en la memoria RAM de la computadora [2] .
Permite una sustitución por partido.
Utiliza el algoritmo Burrows-Wheeler para la indexación. El programa está optimizado para la velocidad y el consumo de memoria, puede usar múltiples núcleos de procesador. Velocidad declarada superior a 35 veces la velocidad de MAQ y 300 veces la velocidad de SOAP en las mismas condiciones. [3]
Permite desajustes.
Basado en Bowtie, se construyó el programa TopHat para alinear las lecturas de RNA-seq.
BWA (Biological Sequence Alignment) es un conjunto de tres programas: BWA-backtrack, BWA-SW y BWA-MEM. BWA-backtrack funciona con lecturas de Illumina de hasta 100 pb, BWA-SW y BWA-MEM pueden funcionar con secuencias más largas de 70 a 1 millón de pb. BWA-MEM es la última versión, de mayor calidad y más precisa.
BWA-SW y BWA-MEM pueden encontrar lecturas quiméricas. [cuatro]
BWA-SW utiliza la transformación de Burrows-Wheeler junto con la ecualización de Smith-Waterman. Capaz de trabajar con secuencias largas, mientras que es más preciso y rápido que BLAT. [5]
Significa alineación local eficiente de datos de nucleótidos. Desarrollado por Solexa, luego adquirido por Illumina.
Utiliza lecturas finales pareadas, es capaz de identificar opciones estructurales. [6] Solo puede trabajar con secuencias de hasta 32 pares de bases, permite hasta dos diferencias, pero no puede trabajar con indeles. [7]
Produce alineación sin huecos. Para lecturas de un solo extremo, puede encontrar hasta 2 o 3 discrepancias según las opciones de lanzamiento. Permite hasta 1 discrepancia para lecturas de extremos emparejados. [ocho]
Construye consenso basado en un modelo estadístico. [9]
Alinea las lecturas de extremo único y extremo emparejado de Illumina, extremo emparejado de 454. Puede detectar alineaciones con lagunas o discrepancias. Puede reportar alineación múltiple. [diez]
SHRiMP2 pone énfasis en la precisión, lo que permite alinear las lecturas con polimorfismos o errores de secuencia.
Utiliza el algoritmo de Smith-Waterman. La versión 1 indexó las lecturas, la versión 2 indexó el genoma, por lo que logró una mayor velocidad.
Admite lecturas Illumina/Solexa, Roche/454 y AB/SOLiD, admite computación paralela. [once]
Puede alinear fragmentos de lectura única y de extremo de par. Capaz de trabajar con intrones.
El algoritmo utiliza el índice 2way-BWT (2BWT) [12] . La versión SOAP3 está optimizada para GPU y utiliza un índice GPU-2BWT especial [13] .
Programa de alineación de lectura de RNA-seq basado en Bowtie.
Fue creado para trabajar con lecturas producidas por Illumina Genome Analyzer, pero se ha utilizado con éxito con lecturas generadas por otras tecnologías. Optimizado para lecturas de longitud de 75 pares de bases o más. No permite que se mezclen lecturas emparejadas y de un solo extremo.
| Programa | Algoritmo | extremo emparejado/extremo único | Brechas (intrones) | indeles | sustituciones | Longitud de lectura (pb) |
|---|---|---|---|---|---|---|
| BFAST | Smith-Waterman. Hay una versión con BWT | +/+ | + | + | ||
| BLAT | Medidas K (como BLAST) | + | 1-2 | 1-2 | ||
| Corbata de moño | Burroughs-Wheeler | -/+ | + | <=100 [14] , 70-1M [15] | ||
| BWA | Burrows-Wheeler + Smith-Waterman | +/+ | + | |||
| ELANDO | ¿Hashing de semillas? | +/? | - | <=2 | hasta 32 | |
| MAQ | hash de semillas | +/+ | - | + [16] | 2-3 [17] para extremo único, 1 para extremo emparejado | <=63 [18] |
| Novoalinear | +/+ | + | + | |||
| Camarón | Medidas K + Smith–Waterman | +/+ | + | + | + | |
| JABÓN | Burroughs-Wheeler | +/+ | + | <=2 | <=60 | |
| sombrero de copa | Burroughs-Wheeler | +/+ [19] | + | + | <=2 [20] | >=75 [21] |