Data structures and algorithms for analyzing DNA sequences in compressed space

Abstract

Los avances en las tecnologías de secuenciación del ADN han generado que hoy en día tengamos una gran cantidad de colecciones genómicas disponibles para analizar. El reto con estas colecciones es almacenar y procesar los datos sin agotar los recursos computacionales. Muchos autores han abordado este desafío utilizando estructuras de datos compactas y algoritmos que explotan las largas repeticiones de ADN en estos datasets. Estas técnicas han demostrado ser eficaces para reducir los elevados costos computacionales. Sin embargo, su uso se ha centrado en genomas ensamblados. Su aplicación a datos de secuenciación sin procesar (también conocidos como lecturas) es un tema menos estudiado. El diseño de estructuras de datos compactas y métodos de compresión para lecturas es una necesidad imperante, dado que estas colecciones genómicas son las más masivas y las más comunes. Esta tesis presenta una infraestructura algorítmica diseñada principalmente para manip- ular colecciones de lecturas en espacio sucinto o comprimido. Nuestro objetivo principal es reducir los altos costos de extraer información biológica a partir de lecturas. Comenzamos introduciendo un nuevo compresor de gramáticas llamado LMSg, el cual está destinado a almacenar lecturas. Nuestro método demuestra ser rápido, altamente paralelizable y con tasas de compresión competitivas con las de compresores populares. Nuestra siguiente contribución es un algoritmo llamado infBWT, el cual calcula la BWT extendida de una colección de lecturas codificadas con la gramática LMSg. El algoritmo utiliza las características de la gramática LMSg y las corridas de símbolos iguales en la BWT para acelerar los cálculos. La BWT extendida es un elemento esencial en muchos autoíndices sucintos que podríamos utilizar para extraer información. Nuestros experimentos muestran que infBWT es más eficiente a medida que las lecturas se vuelven más masivas y repetitivas. Nuestra tercera contribución es un índice sucinto para lecturas cuyo objetivo es extraer información biológica. Esta representación, llamada rBOSS, codifica las lecturas usando un grafo compacto de de Bruijn (BOSS) y una nueva estructura de datos propuesta en esta tesis: el árbol de sobrelape. Además, mostramos que es posible combinar el árbol de sobrelape con la BWT extendida para producir un nuevo autoíndice. Demostramos el uso práctico de rBOSS implementando un algoritmo para ensamblar las lecturas en un genoma. Proponemos un índice sucinto alternativo para lecturas, también pensado para realizar análisis. Esta representación construye un grafo de de Bruijn a partir de las lecturas y asigna un color específico a cada camino en el grafo que represente una lectura. Nuestra contribución es un algoritmo codicioso que reduce el uso de espacio coloreando parcialmente el grafo y dando los mismos colores a diferentes caminos cuando es posible. Además, diseñamos dos algoritmos sobre el índice, uno extrae las lecturas y el otro ensambla el genoma de las lecturas. Nuestra última contribución es un algoritmo práctico para producir una gramática lo- calmente consistente a partir de un texto. Las propiedades de nuestra gramática permiten obtener un índice de gramáticas que mejora la complejidad del tiempo para localizar pa- trones largos, manteniendo altas tasas de compresión. Una característica importante de nuestro algoritmo es que, a diferencia de otras gramáticas localmente consistentes, no necesita estructuras de datos adicionales, como permutaciones, para mantener la consistencia. Esta contribución está pensada para indexar colecciones de genomas completos en el futuro.