Agregando búsquedas sobre colecciones genómicas en formato VCF

Abstract

Cuando se trata de hacer estudios de variantes en el genoma, el principal formato que se utiliza para representar la información de interés es el Variant Calling Format (VCF). La principal característica de VCF es que almacena el genoma de un conjunto de individuos en base a las variantes (edits) que tiene con respecto a un genoma de referencia. Si bien este formato hace buen uso de que el genoma de individuos tiene más semejanzas que diferencias, cuando se trata de realizar consultas sobre los genomas que este representa, VCF no da abasto de forma eficiente. Si quisiéramos buscar la ocurrencia de un patrón dentro de VCF, deberíamos recrear la cadena, es decir descomprimir VCF, y sobre ella buscar. Esto es impracticable sobre grandes colecciones genómicas. Ahora, el problema descrito corresponde a una tarea bastante estudiada en computación, que es la búsqueda de patrones sobre textos de alta repetitividad. Como respuesta a este problema se han desarrollado los índices comprimidos para colecciones repetitivas, donde uno de sus exponentes posee un proceso de construcción análogo a la forma de trabajo de VCF. Este \'indice corresponde a Relative Lempel-Ziv (RLZ), el cual nos permite realizar búsquedas sobre el texto indexado sin nunca descomprimirlo. En este Trabajo de Título se busca soportar búsquedas sobre colecciones genómicas en formato VCF sin descomprimir. Para hacer esto posible, se diseña e implementa un módulo de conversión de VCF a RLZ, el cual a partir de la construcción de este índice permite realizar búsquedas y entregar posiciones de ocurrencias en un formato concordante a la información que representa VCF. Esta conversión se hace sin descomprimir el VCF. La solución implementada consta de tres etapas de procesamiento de VCF: caracterización de edits, agrupación de caracterizaciones e interpretación de caracterizaciones para construir RLZ. En paralelo, a partir de la interpretación generamos una estructura de datos compacta extra que nos permitirá soportar la transformación de posiciones de ocurrencia en RLZ a VCF. Se utilizó una implementación de RLZ proveída por los profesores guía, donde con el fin de no requerir la cadena original para su construcción, se editó el constructor del índice. Este módulo fue validado sobre distintos datasets generados a partir de los VCF publicados por el proyecto 1000 Genomes, con el fin de evaluar los tiempos de conversión y volumen de los productos. El módulo cumplió con el objetivo propuesto, procesando hasta 72 genomas humanos en 6 horas, y dejando la información lista para ser consumida por RLZ. Sin embargo, el ordenamiento de prefijos y sufijos requerida por el índice RLZ significó un cuello de botella significativo en los tiempos de construcción. Se consiguió indexar el cromosoma 21 hasta para 12 individuos en 11 horas y demostrar la funcionalidad de las búsquedas.