Read mapping on heterogeneous systems: scalability strategies for bioinformatic primitives

Abstract

La seqüenciació genòmica és un component clau en nous avenços en medicina, i la seva democratització és un pas important per millorar l’accessibilitat per al pacient. Els beneficis implícits en el descobriment de noves variants genètiques són molt amplis, incloent des de la detecció precoç de càncer com la medicina personalitzada, passant pel disseny de fàrmacs i l’edició genòmica. Tots aquests usos potencials han incrementat exponencialment l’interès de la comunitat científica en el camp de la bioinformàtica durant els últims anys. A més, el sorgiment dels mètodes de Seqüenciació de Nova Generació ha contribuït a la reducció ràpida dels costos de seqüenciació, permetent el desenvolupament de noves aplicacions genòmiques. El principal objectiu d’aquesta tesi és el de millorar el rendiment i precisió de l’estat de l’art de la seqüenciació genètica a través de l’ús de plataformes de còmput heterogeni i sistemes de computació híbrida. Més específicament, el treball s’ha centrat en l’acceleració de el problema de mapeig de reads curts, ja que es descriu com un dels estadis del pipeline amb un major cost computacional. De forma global, s’ aspirava a reduir el temps de processament i el cost de la seqüenciació genètica, incrementant la disponibilitat d’aquest tipus d’anàlisi. La principal contribució d’aquesta tesi és la integració GPU del mapper GEM3 (GEM3-GPU). Aquest mapper reporta les mateixes dades de sortida per CPU i GPU, i és un dels primers mappers GPU que permet l’alineament de reads llargs i variables. Les propostes han estat validades utilitzant dades reals, ja que el mapper ha estat corrent en producció en un centre de seqüenciació genòmica (Centre Nacional d’Anàlisi Genòmica (CNAG)). En conjunció amb el mapper GEM3-GPU, durant aquesta tesi s’ha creat una llibreria bioinformàtica en CUDA (GEM-cutter). La llibreria aporta blocs de primitives GPU bàsiques que han estat altament optimitzades. Gem-cutter ofereix una API basada en primitives send and receive (message passing), i incorpora un scheduler per balancejar el treball. A més, la llibreria suporta totes les arquitectures GPU i Multi-GPU.

La secuenciación genómica es un componente clave en nuevos avances en medicina, y su democratización es un paso importante hacia la accesibilidad para el paciente. Los beneficios implícitos en el descubrimiento de nuevas variantes genéticas son muy amplios, incluyendo desde la detección precoz de cáncer como la medicina personalizada, pasando por el diseño de fármaco y la edición genómica. Estos usos potenciales han incrementado exponencialmente el interés de la comunidad científica en el campo de la bioinformática durante los últimos años. Además, el surgimiento de los métodos de Secuenciación de Nueva Generación ha contribuido a la reducción rápida de los costes de secuenciación, permitiendo el desarrollo de nuevas aplicaciones genómicas. El principal objetivo de esta tesis es el de mejorar el rendimiento y precisión del estado del arte de la secuenciación genética a través del uso de plataformas de computo heterogéneo y sistemas de hardware híbridos. Más específicamente, el trabajo se ha centrado en la aceleración del problema del short-read mapping, dado que se describe como uno de los estadíos del pipeline con un mayor coste computacional. De forma global, se aspiraba a reducir el tiempo de procesado y el coste de la secuenciación genética, incrementando su disponibilidad. La principal contribución de esta tesis es la integración GPU del mapper GEM3 (GEM3-GPU). Este mapper reporta los mismos datos de salida para CPU y GPU, y es uno de los primeros mappers GPU que permite el alineamiento de reads largos y variables. Las propuestas han sido validadas utilizando datos reales, dado que el mapper ha estado corriendo en producción en un centro de secuenciación (Centro Nacional de Análisis Genómico (CNAG)). En conjunción con el mapper GEM3-GPU, durante esta tesis se ha creado una librería bioinformática en CUDA (GEM-cutter). La librería provee bloques de primitivas GPU básicas que han sido altamente optimizadas. Gem-cutter ofrece una API basada en primitivas de send and receive (message passing), e incorpora un scheduler para balancear el trabajo. Además, la librería soporta todas las arquitecturas GPU y Multi-GPU.

Genomic sequencing is the key component of new advances in medicine, and its democratization is an important step in improving accessibility for the patient. The benefits involved in discovering new genomic variations are vast and include everything from early cancer detection to personalized medicine, drug design and genome editing. All of these potential uses have greatly increased the interest of the scientific community in the field of bioinformatics in recent years. Moreover, the emergence of next-generation sequencing methods has contributed to the rapid reduction of sequencing costs, enabling new applications of genomics in precision medicine. The main goal of this thesis is to improve the state of the art in performance and accuracy for genome sequencing through the use of heterogeneous computing platforms and hybrid hardware systems. More specifically, the work is focused on accelerating the problem of short-read mapping, as it is described as one of the most computationally expensive parts of the pipeline process. Overall, we aim to reduce the processing time and cost of genome sequencing, and then increasing the availability of this type analysis. The main contribution of this thesis is the full GPU integration of the GEM3 mapper (GEM3-GPU), reporting significant improvements in performance and competitive accuracy results. The mapper reports the same output files for CPU and GPU and is one of the first GPU mappers to allow very long and variable read alignment. The proposals have been validated using real data, since the mapper has been running in production at a genomic sequencing center (Centro Nacional de Análisis Genómico (CNAG)). Together with the GEM3-GPU mapper, a complete bioinformatics CUDA library (GEM-cutter) has been created. The library provides the basic building blocks for genomic applications, which are highly optimised to run on GPUs. Gem-cutter offers an API based on send and receive primitives (message passing) and incorporates a scheduler to balance the work. Furthermore, the library supports all GPU architectures and Multi-GPU execution.