Algoritmos y arquitectura para cálculo de similitudes genómicas en aceleradores en hardware.
Loading...
Date
2023
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad de Concepción.
Abstract
La similitud entre genomas es un concepto fundamental en bioinformática. Esta se utiliza para determinar relaciones evolutivas o filogenéticas entre diferentes especies, para identificar regiones similares en genomas, o para organizar genomas con características genéticas similares en grupos o clústeres. Existen diversas métricas de comparación utilizadas en la literatura, las cuales utilizan diferentes principios para medir la similitud. Una de las más utilizadas en genómica es la similitud de Jaccard, la que se basa en teoría de conjuntos y evalúa la presencia o ausencia de elementos en los dos conjuntos a comparar para indicar qué tan similares son. Otra métrica utilizada es la divergencia de Jensen-Shannon, que usa información estadística asociada a la distribución de probabilidad de un genoma, que puede estar representado por más de una secuencia. En general, el procesamiento de genomas se realiza describiéndolos como un conjunto de substrings de largo k, llamados k-mers. Tanto el proceso de extracción de k-mers como el cálculo de similitud, son tareas computacionalmente desafiantes, debido al alto uso de memoria requerida por el volumen de datos asociado a datos genómicos y a la complejidad cuadrática del cálculo de similitud entre pares. Este trabajo presenta el diseño de algoritmos y aceleradores usando el paradigma de FPGAas-a-service para calcular la similitud entre genomas utilizando estructuras de datos probabilísticas o sketches. El primer acelerador realiza el cálculo de similitud Jaccard entre genomas, pudiendo calcular todas las similitudes entre los elementos de una base de datos o solo aquellos que tengan la posibilidad de superar cierto umbral, permitiendo así reducir significativamente la cantidad de operaciones a realizar. Después de la construcción de sketches, el acelerador puede calcular más de 96 millones de coeficientes Jaccard por segundo en una instancia f1.2xlarge de Amazon Web Services (AWS) con un FPGA XCVU9P, lo que presenta una aceleración de 58 veces sobre el estado del arte en software corriendo en una instancia c5.9xlarge. El acelerador es 27 veces más rápido que una implementación directa en GPU y 4 veces más rápido que una implementación optimizada en GPU, correspondiente a una adaptación del algoritmo diseñado para el FPGA. Ambas implementaciones en GPU fueron evaluadas en una instancia g5.4xlarge que cuenta con una GPU NVIDIA A10G. El segundo acelerador implementa el cálculo de similitud usando divergencia de Jensen-Shannon. El acelerador utiliza una estructura llamada arreglo de colas de prioridad (PQA), la cual almacena los elementos más frecuentes de un conjunto para el cálculo de entropía. Esta implementación alcanza una aceleración de 1, 9 veces comparada con la implementación del mismo algoritmo en GPU, en ambos casos usando las instancias f1.2xlarge y g5.4xlarge respectivamente.
Description
Tesis para optar al grado de Doctor en Ciencias de la Ingeniería con mención en Ingeniería Eléctrica.