Computación de alto desempeño aplicada al procesamiento de grandes volúmenes de datos genómicos

Abstract

El cómputo de distancias entre vectores es un problema relevante en el ámbito de la bioinformática, utilizado principalmente en diversas etapas en el análisis de datos genómicos. A pesar de que existen implementaciones de alto desempeño, muchas de ellas no explotan características particulares del problema biológico, y, por ello, no aprovechan plenamente los recursos de cómputo al trabajar con conjuntos de datos a gran escala. En este trabajo, diseñamos, implementamos y evaluamos diferentes algoritmos que aprovechan propiedades específicas de los datos genómicos en plataformas CPU y GPU, obteniendo mejoras significativas tanto en el uso de memoria como en la eficiencia computacional respecto a los métodos de referencia del estado del arte. En particular, proponemos un esquema de codificación de los datos que reduce sustancialmente el uso de memoria y permite explotar de manera efectiva la jerarquía de memoria de los recursos de cómputo. A partir de este esquema derivamos un método eficiente para la comparación de secuencias de ADN, capaz de reproducir el resultado equivalente al de la distancia euclidiana, utilizando únicamente una cantidad mínima de operaciones bit a bit. Asimismo, se realizaron optimizaciones sobre el algoritmo R-Kleene que explotan la simetría del problema. Por otra parte, los algoritmos desarrollados pueden adaptarse fácilmente a arquitecturas híbridas y al procesamiento por lotes, gracias a la descomposición natural del problema. Finalmente, realizamos una evaluación experimental para analizar el desempeño computacional de las propuestas, obteniendo mejoras significativas sobre los algoritmos utilizados como línea base.