Algoritmos de ensamblaje en bioinformática

En la tesis doctoral de Guerrero Fernández, publicada el año 2015 con el título “Plataforma de supercomputación para bioinformática”, se explica que el problema del ensamblaje está lejos de solucionarse, al menos hasta que la tecnología de secuenciación a tiempo real de una única molécula de acido desoxirribonucleico baje del trece por ciento de error que presenta actualmente. Finotello y sus colegas, en el artículo publicado el año 2012 con el título “Análisis comparativo de algoritmos para el ensamblado de genomas completos de datos pirosecuenciados”, mencionan que no todos los organismos se ensamblan con la misma facilidad, ni todos los ensambladores funcionan igual en todos los organismos. Para ensamblar dos lecturas hay que detectar las regiones en las que solapan, que deben tener una longitud mínima para ser fiables, siempre teniendo en cuenta el tamaño de las lecturas que se tienen disponibles. Si son lecturas de cincuenta nucleótidos de longitud no sería razonable exigir un solapamiento de cuarenta nucleótidos, mientras que ese solapamiento sí es perfectamente válido para ensamblar lecturas largas. Por la forma de detectar estas regiones solapantes, es posible encontrar diferentes tipos de algoritmos, entre los cuales destacan: (1) Algoritmo de Greedy, (2) algoritmos voraces, (3) algoritmos de superposición/presentación/consenso y (4) algoritmos basados en grafos de De Bruijn.

Nagarajan y Pop, en el artículo publicado el año 2013 titulado “Ensamblado de secuencias desmitificado”, mencionan que Greedy es el algoritmo más sencillo e intuitivo para el ensamblado de secuencias. El ensamblador siempre conecta las lecturas que mejor se solapan, de manera iterativa, mientras no contradigan el ensamblaje ya construido. Sin embargo, esta metodología no es ampliamente empleada, ya que es inherentemente un proceso de ensamblaje local, no emplea información global, y no resuelve de manera eficiente largas regiones repetitivas en los genomas. Greedy se utiliza generalmente para el ensamblaje de datos originados por secuenciación Sanger. En los algoritmos de ensamblaje voraces se parte de una lectura inicial y después se selecciona el mejor candidato entre el resto de lecturas para extender la cadena. El mejor candidato será aquella lectura que solape más nucleótidos con la lectura inicial. El proceso se repite de forma iterativa tomando como secuencia inicial el resultado de la iteración anterior, hasta que ya no queden más candidatos posibles para extender la cadena. Aunque no se construya una estructura de grafos propiamente dicha, sí que se está recorriendo un grafo virtual al realizar en cada paso la búsqueda del mejor candidato. Este sistema de ensamblaje es el más primitivo de todos y presenta claros problemas con las zonas repetitivas, que quedarían reducidas a una sola repetición. Algoritmos que encajan en esta categoría son SSAKE, descrito en el artículo de Warren y Holt, publicado el año 2008 con el título “SSAKE 3.0 mejora de la velocidad, la precisión y la contigüidad”; VCAKE, explicado en el artículo de Jeck y sus colegas, publicado el año 2007 con el título “Extensión del ensamblado de secuencias pequeñas de ADN para manejar el error”; SHARCGS, detallado en el artículo de Dohm y sus colegas, publicado el año 2007 con el título “SHARCGS, un algoritmo de montaje de lectura corta, rápida y de alta precisión para la secuenciación del genoma de novo”.

La aproximación del algoritmo de superposición/presentación/consenso se realiza en tres etapas: (1) En la primera etapa se buscan las regiones solapantes entre secuencias, para lo cual se realiza una comparación de cada secuencia contra todas las demás. Esta comparación se realiza en función de los porcentajes de identidad y del tamaño mínimo del solapamiento junto con un parámetro muy importante para los ensamblajes denominado tamaño de k-mero, que normalmente elige el usuario, pero otras veces se encuentra fijado en el código fuente del algoritmo. El tamaño de k-mero puede ser considerado como la unidad básica de comparación que se utilizará en la búsqueda de solapamientos. Al utilizar un k-mero de longitud n, se calculan todas las posibles combinaciones de nucleótidos de dicha longitud, y después se procesan todas las lecturas determinando los k-meros que contienen en común entre ellas. Esta abstracción acelera los procesos de ensamblaje y permite un ahorro considerable de memoria. (2) En la segunda etapa se procesa el grafo de las relaciones establecidas entre las lecturas para establecer la forma más probable del ensamblaje atendiendo al número de k-meros que comparten los posibles solapamientos. (3) Finalmente se alinean las secuencias que solapan entre sí para elegir las secuencias consenso que serán los contigs resultantes del ensamblaje. Algunos ensambladores que utilizan esta aproximación son Celera Assembler, descrito en el artículo de Myers y sus colegas, publicado el año 2000 con el título “Ensamblado completo del genoma Drosophila”; Arachne, detallado en el artículo de Batzoglou y sus colegas, publicado el año 2002 con el título “Ensamblado de arma de fuego completo del genoma”; CAP y PCAP, descritos por Huang y Yang en el capítulo titulado “Generando ensamblado de genomas con PCAP”, publicado el año 2005.

Un grafo de De Bruijn se utiliza para representar solapamientos entre cadenas de símbolos, lo cual encaja perfectamente con el problema del ensamblaje. Los ensambladores basados en grafos de De Bruijn suelen utilizarse para lecturas cortas. La forma simplificada de cómo se añade cada lectura al grafo es la siguiente, primero se divide en oligomeros de un tamaño k elegido por el usuario, y de cada k-mero se extraen los extremos izquierdo y derecho de tamaño k-1, extremos que se almacenan como nuevos nodos en el grafo de De Bruijn unidos entre sí con un arco dirigido desde el extremo izquierdo al derecho. Si los nodos ya existen en el grafo, únicamente se añade el arco que los une. La secuencia ensamblada se obtiene recorriendo el grafo desde el extremo inicial hasta el final, concatenando la primera base del k-mero almacenado en cada uno de los nodos recorridos, excepto el k-mero del nodo final que se une por completo al resultado. Al formar el grafo mediante la adición de las lecturas de forma iterativa, se evita hacer comparaciones de todas las secuencias entre sí. Además es habitual que las secuencias no se almacenen en el grafo y que las repeticiones sean anotadas con un contador numérico en vez de utilizar arcos adicionales, estrategias que ayudan a ahorrar memoria durante la ejecución del algoritmo. Ensambladores que usan esta técnica son: Velvet, descrito en el artículo de Zerbino y Birney, publicado el año 2008 con el título “Velvet: Algoritmos para el ensamblado de lectura corta utilizando el grafo de De Bruijn”; ABySS, detallado en el artículo de Simpson y sus colegas, publicado el año 2009 con el título “ABySS: Ensamblador paralelo para lectura corta de datos secuenciados”; AllPaths, explicado en el artículo de Butler y sus colegas, publicado el año 2008 con el título “AllPaths: Ensamblado de novo para micro lecturas del genoma completo”; además de SOAPdenovo, descrito en el artículo de Li y sus colegas, publicado el año 2009 con el título “Ensamblado de novo del genoma humano con secuencia de lectura corta masivamente paralela”.