Search

One of the outstanding milestones achieved in recent years in the field of biotechnology research has been the development of high-throughput sequencing (HTS). Due to the fact that at the moment it is technically impossible to decode the genome as a whole, HTS technologies read billions of relatively short chunks of a genome at random locations. Such reads then need to be located within a reference for the species being studied (that is aligned or mapped to the genome): for each read one identifies in the reference regions that share a large sequence similarity with it, therefore indicating what the read¿s point or points of origin may be. HTS technologies are able to re-sequence a human individual (i.e. to establish the differences between his/her individual genome and the reference genome for the human species) in a very short period of time. They have also paved the way for the development of a number of new protocols and methods, leading to novel insights in genomics and biology in general. However, HTS technologies also pose a challenge to traditional data analysis methods; this is due to the sheer amount of data to be processed and the need for improved alignment algorithms that can generate accurate results quickly. This thesis tackles the problem of sequence alignment as a step within the analysis of HTS data. Its contributions focus on both the methodological aspects and the algorithmic challenges towards efficient, scalable, and accurate HTS mapping. From a methodological standpoint, this thesis strives to establish a comprehensive framework able to assess the quality of HTS mapping results. In order to be able to do so one has to understand the source and nature of mapping conflicts, and explore the accuracy limits inherent in how sequence alignment is performed for current HTS technologies. From an algorithmic standpoint, this work introduces state-of-the-art index structures and approximate string matching algorithms. They contribute novel insights that can be used in practical applications towards efficient and accurate read mapping. More in detail, first we present methods able to reduce the storage space taken by indexes for genome-scale references, while still providing fast query access in order to support effective search algorithms. Second, we describe novel filtering techniques that vastly reduce the computational requirements of sequence mapping, but are nonetheless capable of giving strict algorithmic guarantees on the completeness of the results. Finally, this thesis presents new incremental algorithmic techniques able to combine several approximate string matching algorithms; this leads to efficient and flexible search algorithms allowing the user to reach arbitrary search depths. All algorithms and methodological contributions of this thesis have been implemented as components of a production aligner, the GEM-mapper, which is publicly available, widely used worldwide and cited by a sizeable body of literature. It offers flexible and accurate sequence mapping while outperforming other HTS mappers both as to running time and to the quality of the results it produces., Uno de los avances más importantes de los últimos años en el campo de la biotecnología ha sido el desarrollo de las llamadas técnicas de secuenciación de alto rendimiento (high-throughput sequencing, HTS). Debido a las limitaciones técnicas para secuenciar un genoma, las técnicas de alto rendimiento secuencian individualmente billones de pequeñas partes del genoma provenientes de regiones aleatorias. Posteriormente, estas pequeñas secuencias han de ser localizadas en el genoma de referencia del organismo en cuestión. Este proceso se denomina alineamiento - o mapeado - y consiste en identificar aquellas regiones del genoma de referencia que comparten una alta similaridad con las lecturas producidas por el secuenciador. De esta manera, en cuestión de horas, la secuenciación de alto rendimiento puede secuenciar un individuo y establecer las diferencias de este con el resto de la especie. En última instancia, estas tecnologías han potenciado nuevos protocolos y metodologías de investigación con un profundo impacto en el campo de la genómica, la medicina y la biología en general. La secuenciación alto rendimiento, sin embargo, supone un reto para los procesos tradicionales de análisis de datos. Debido a la elevada cantidad de datos a analizar, se necesitan nuevas y mejoradas técnicas algorítmicas que puedan escalar con el volumen de datos y producir resultados precisos. Esta tesis aborda dicho problema. Las contribuciones que en ella se realizan se enfocan desde una perspectiva metodológica y otra algorítmica que propone el desarrollo de nuevos algoritmos y técnicas que permitan alinear secuencias de manera eficiente, precisa y escalable. Desde el punto de vista metodológico, esta tesis analiza y propone un marco de referencia para evaluar la calidad de los resultados del alineamiento de secuencias. Para ello, se analiza el origen de los conflictos durante la alineación de secuencias y se exploran los límites alcanzables en calidad con las tecnologías de secuenciación de alto rendimiento. Desde el punto de vista algorítmico, en el contexto de la búsqueda aproximada de patrones, esta tesis propone nuevas técnicas algorítmicas y de diseño de índices con el objetivo de mejorar la calidad y el desempeño de las herramientas dedicadas a alinear secuencias. En concreto, esta tesis presenta técnicas de diseño de índices genómicos enfocados a obtener un acceso más eficiente y escalable. También se presentan nuevas técnicas algorítmicas de filtrado con el fin de reducir el tiempo de ejecución necesario para alinear secuencias. Y, por último, se proponen algoritmos incrementales y técnicas híbridas para combinar métodos de alineamiento y mejorar el rendimiento en búsquedas donde el error esperado es alto. Todo ello sin degradar la calidad de los resultados y con garantías formales de precisión. Para concluir, es preciso apuntar que todos los algoritmos y metodologías propuestos en esta tesis están implementados y forman parte del alineador GEM. Este versátil alineador ofrece resultados de alta calidad en entornos de producción siendo varias veces más rápido que otros alineadores. En la actualidad este software se ofrece gratuitamente, tiene una amplia comunidad de usuarios y ha sido citado en numerosas publicaciones científicas.

Supplementary Tables, Figures and Methods (PDF 717 kb)

Junction sequences for 3 RT-PCR validated chimeras (DOCX 4.39 kb)

La librería GEM, que utiliza la transformada de Burrows-Wheeler y los índices de Ferragina-Manzini, es utilizada por los centros de investigación genómica para indexar grandes cantidades de pequeñas secuencias de DNA. Esta librería proporciona un conjunto de operaciones para anlizar de forma eficiente las secuencias dentro de un índice genómico. Por ello, se busca maximizar el rendimiento de esta aplicación en el entorno de producción. Este Proyecto Fin de Carrera consiste en analizar y evaluar la librería, sus estructuras y mecanismos de indexación. Se analiza su rendimiento y comportamiento en memoria prestando especial atención al uso que realiza de la jerarquía de memoria. Así bien, se muestra cuales son los cuellos de botella. Además, se plantean alternativas de implementación enfocadas a mejorar el rendimiento de la librería. Se proponen mejoras tanto a nivel algoritmo como consientes de la arquitectura. Una vez expuesto el análisis sobre la librería se exponen los resultados derivados de la implementación de las optimizaciones. Se muestran los resultados de ajustar los parámetros de optimización, los costes y resultados. De este modo, se analiza desde una perspectiva cualitativa y cuantitativa el impacto de las optimizaciones en la librería y porque ayudan a mejorar el rendimiento global de la librería. Por otro lado, se exponen los resultados de varios estudios relacionados con el impacto de las opciones de compilación en la librería, la organización a bajo nivel del índice en memoria, la distribución de las bases en el índice y la implementación de operaciones en el camino crítico de la aplicación. Por último, se realiza una aproximación a una versión paralela de la librería. Esta ha sido implementada y evaluada en términos de rendimiento y escalabilidad. Se justifica la solución adoptada y los resultados obtenidos. Se finaliza haciendo una evaluación del trabajo realizado y el planteamiento de objetivos en la línea del presente Proyecto Fin de Carrera.

UBA2-WTIP transcript isoform sequences (DOCX 142kb)

UBA2-WTIP transcript isoform sequences (DOCX 142kb)

El emparejamiento de secuencias genéticas se puede definir como la búsqueda de las diferencias que existen entre dos cadenas de caracteres: patrón y texto. Existe una gran variedad de algoritmos que resuelven este problema con diferentes costes computacionales. En este trabajo se consideran algoritmos de emparejamiento de tipo exacto y, utilizando técnicas de la Ingeniería de Rendimiento, se mejora la eficiencia de codificación de los mismos. Se obtiene un Speed Up de 3,7x para un algoritmo basado en el peor caso y un Speed Up de 8x en un algoritmo basado en casos medios. Como resultado final se obtiene una versión del programa con un Speed Up de 114x frente a la versión base, para un patrón de 10k caracteres y un texto con el 20% de error respecto al patrón. The matching of genetic sequences can be defined as the search for the differences between two-character strings: pattern and text. A great variety of algorithms can solve this problem with different computational costs. This work studies two exact string matching algorithms and, using Performance Engineering techniques, improves its coding efficiency, attaining a Speed Up of 3,7x for a worst case based algorithm and a Speed Up of 8x on an average case algorithm. As a final result a version with an Speed Up of 114x is achieved compared to the base version, for a 10k character pattern and a text with a 20% difference compared to the pattern. L'aparellament de seqüències genètiques es pot definir com la recerca de les diferències que hi ha entre dues cadenes de caràcters: patró i text. Hi ha una gran varietat d'algoritmes que resolen aquest problema amb diferents costos computacionals. En aquest treball es consideren algoritmes d'aparellament de tipus exacte i, utilitzant tècniques de l'Enginyeria de Rendiment, es millora l'eficiència de codificació dels mateixos. S'obté un Speed Up de 3,7x per a un algoritme basat en el pitjor cas i un Speed Up de 8x en un algoritme basat en casos mitjans. Com a resultat final s'obté una versió del programa amb un Speed Up de 114x enfront de la versió base, per a un patró de 10k caràcters i un text amb el 20% d'error respecte al patró.

Arm usage has substantially grown in the High-Performance Computing (HPC) community. Japanese supercomputer Fugaku, powered by Arm-based A64FX processors, held the top position on the Top500 list between June 2020 and June 2022, currently sitting in the second position. The recently released 7th generation of Amazon EC2 instances for compute-intensive workloads (C7g) is also powered by Arm Graviton3 processors. Projects like European Mont-Blanc and U.S. DOE/NNSA Astra are further examples of Arm irruption in HPC. In parallel, over the last decade, the rapid improvement of genomic sequencing technologies and the exponential growth of sequencing data has placed a significant bottleneck on the computational side. While the majority of genomics applications have been thoroughly tested and optimized for x86 systems, just a few are prepared to perform efficiently on Arm machines, let alone exploit the advantages of the newly introduced Scalable Vector Extensions (SVE). This thesis presents GenArchBench, the first genome analysis benchmark suite targeting Arm architectures. We have selected a set of computationally demanding kernels from the most widely used tools in genome data analysis and ported them to Arm-based A64FX and Graviton3 processors. The porting features the usage of the novel Arm SVE instructions, algorithmic and code optimizations, and the exploitation of Arm-optimized libraries. All in all, the GenArch benchmark suite comprises 13 multi-core kernels from critical stages of widely-used genome analysis pipelines, including base-calling, read mapping, variant calling, and genome assembly. Moreover, our benchmark suite includes different input data sets per kernel (small and large), each with a corresponding regression test to verify the correctness of each execution automatically. In this work, we present the optimizations implemented in each kernel and a detailed performance evaluation and comparison of their performance on four different architectures (i.e., A64FX, Graviton3, Intel Xeon Platinum, and AMD EPYC). Additionally, as proof of the impact of this work, we study the performance improvement in a production-ready genomics pipeline using the GenArchBench optimized kernels.

Actualmente, gem5 está visto como el estándar de simulación para obtener métricas de rendimiento de computadores. La infraestructura de simulación gem5 combina los aspectos más destacados de los simuladores M5 y GEMS, ofreciendo un marco de simulación altamente configurable, múltiples ISAs y diversos modelos de CPU, así como un sistema de memoria detallado y flexible, que incluye soporte para múltiples protocolos de coherencia de caché y modelos de interconexión. En el presente artículo se realizará un estudio sobre gem5 y sus posibilidades, y posteriormente, se mostrará el diseño y desarrollo realizado para tener la infraestructura para simular una arquitectura actual y poder comparar sus dos formas principales para modelar jerarquias de memoria: Ruby y classic. Actualment, gem5 està vist com l'estàndard de simulació per obtenir mètriques de rendiment de computadors. La infraestructura de simulació gem5 combina els aspectes més destacats dels simuladors M5 i GEMS, oferint un marc de simulació altament configurable, múltiples ISAs i diversos models de CPU, així com un sistema de memòria detallat i flexible, que inclou suport per a múltiples protocols de coherència de memòria cau i models d'interconnexió. En aquest article es realitzarà un estudi sobre gem5 i les seves possibilitats, i posteriorment, es mostrarà el disseny i desenvolupament realitzat per tenir la infraestructura per simular una arquitectura actual i poder comparar les dues formes principals per modelar jerarquies de memòria: Ruby i classic. Nowadays, gem5 is seen as the simulation standard for obtaining computer performance metrics. The gem5 simulation infrastructure combines the highlights of the M5 and GEMS simulators, providing both a highly configurable simulation framework, multiple ISAs and various CPU models, and complementing these features with a detailed and flexible memory system, including support for multiple cache coherence protocols and interconnection models. In this article we will make a study about gem5 and its possibilities, and then we will show the design and development effort undertaken to have a simulation infrastructure able to model a modern architecture. The infrastructure is used to compare the two main ways to model the memory hierarchy: Ruby and classic.

Advances in genomics and sequencing technologies demand faster and more scalable analysis methods that can process longer sequences with higher accuracy. However, classical pairwise alignment methods, based on dynamic programming (DP), impose impractical computational requirements to align long and noisy sequences like those produced by PacBio, and Nanopore technologies. The recently proposed Wavefront Alignment (WFA) algorithm paves the way for more efficient alignment tools, improving time and memory complexity over previous methods. Notwithstanding the advantages of the WFA algorithm, modern high performance computing (HPC) platforms rely on accelerator-based architectures that exploit parallel computing resources to improve over classical computing CPUs. Hence, a GPU-enabled implementation of the WFA could exploit the hardware resources of modern GPUs and further accelerate sequence alignment in current genome analysis pipelines. This thesis presents two GPU-accelerated implementations based on the WFA for fast pairwise DNA sequence alignment: eWFA-GPU and WFA-GPU. Our first proposal, eWFA-GPU, computes the exact edit-distance alignment between two short sequences (up to a few thousand bases), taking full advantage of the massive parallel capabilities of modern GPUs. We propose a succinct representation of the alignment data that successfully reduces the overall amount of memory required, allowing the exploitation of the fast on-chip memory of a GPU. Our results show that eWFA-GPU outperforms by 3-9X the edit-distance WFA implementation running on a 20 core machine. Compared to other state-of-the-art tools computing the edit-distance, eWFA-GPU is up to 265X faster than CPU tools and up to 56 times faster than other GPU-enabled implementations. Our second contribution, the WFA-GPU tool, extends the work of eWFA-GPU to compute the exact gap-affine distance (i.e., a more general alignment problem) between arbitrary long sequences. In this work, we propose a CPU-GPU co-design capable of performing inter and intra-sequence parallel alignment of multiple sequences, combining a succinct WFA-data representation with an efficient GPU implementation. As a result, we demonstrate that our implementation outperforms the original WFA implementation between 1.5-7.7X times when computing the alignment path, and between 2.6-16X when computing only the alignment score. Moreover, compared to other state-of-the-art tools, the WFA-GPU is up to 26.7X faster than other GPU implementations and up to four orders of magnitude faster than other CPU implementations.

Nowadays, the efficient analysis and exploitation of genomic information is paramount to future advancements in the healthcare sector, such as better diagnosis techniques and the development of improved disease treatments. In the past decades, the exponential increase in the biological data production has fostered the development of more efficient genomic pipelines. For that, modern genome analysis requires better and more scalable algorithms, and improved high-performance implementations that can exploit current hardware accelerators. For most genome analysis pipelines, sequence mapping is one of the most computationally intensive and time-consuming processing stages. The ultimate goal of this work is to propose techniques to accelerate read mapping, leveraging novel algorithms and hardware vector extensions. In this thesis, we present a thorough performance characterization of the most widely-used genome-mapping tools and propose acceleration techniques that can effectively improve the performance of these tools. To that end, first, we identify the most time-consuming kernels, their performance bottlenecks, and the underlying causes of inefficiency. Afterwards, we design and implement an accelerated version of one of the most time-consuming steps: pairwise sequence alignment. For that, we propose to replace the classical dynamic-programming algorithm, used within these tools, with the recently proposed wavefront alignment algorithm (WFA). Moreover, we design and implement the first fully-vectorized version of the WFA, leveraging Intel's AVX2 and AVX-512 instructions, to further accelerate sequence-to-sequence alignment. As a result, we demonstrate that our vectorized WFA implementation outperforms the original scalar WFA implementation between 1.1x-2.4x. In turn, this renders speedups from 2.4x up to 826.7x compared to the most widely-used alignment algorithm, KSW2 (used within Minimap2 and Bwa-Mem2). We conclude that these tools can be significantly accelerated by selecting better algorithms (like the WFA) and leveraging fine-tuned implementations that can exploit hardware resources available in current high performance computing (HPC) processors.

For the past decade, machine learning (ML) has revolutionized numerous domains in our daily life. Nowadays, deep learning (DL) algorithms are the central focus of modern ML systems. As a result, we are witnessing an impressive surge of DL libraries and customized hardware designs that can efficiently support this computing-intensive techniques. The ever increasing development of new libraries and hardware designs rises a new challenge: how to create a fair comparison between the various implementations of DL libraries exploiting different hardware designs. Being able to compare these solutions is a key element to drive the design of new features and better exploit different hardware designs. To improve DL libraries, we need to adopt a common benchmark for the evaluation of the many DL frameworks in terms of accuracy and performance. A standardized benchmark would produce a fair and comprehensive evaluation of all the available methods, paving the way for better hardware-specific designs. However, benchmarking ML methods presents a number of unique challenges. First, some optimization techniques improve training accuracy at the cost of increasing "time to solution". Also, training is an stochastic process and "time to solution" depicts a high variability. Last, there are multiple software and hardware systems and it is not straightforward how to fairly evaluate them under the same parameters. MLPerf training benchmark defines guidelines to mitigate these challenges. MLPerf's mission is to build a fair and useful benchmarks for measuring performance of ML hardware, software, and services. The benchmark measures how fast systems can train models to a target quality. The first release (v0.5) contains seven different DL suites across four domains: (1) vision, (2) language, (3) commerce, and (4) research. Each of these suites is defined by a dataset, a quality target, and a reference implementation model. In this work, we present an image classification evaluation based on MLPerf benchmark for three DL libraries: Keras-TF, PyTorch, and the European Distributed Deep Learning Library (EDDLL). Keras and PyTorch have become very popular and widely-used libraries in the DL field. Meanwhile EDDLL is a novel library being developed as a part of the European project DeepHealth. Our goal is to perform a unified performance evaluation and characterization of these DL frameworks using the High Performance Computing (HPC) infrastructures of the BSC. The present work aims to help improving the EDDL library. We dive into the core implementation of the library to identify potential bottlenecks and explore optimization opportunities. This way, this work establishes the foundations for the EDDL CPU-optimized version, adapted to the HPC hardware infrastructure without compromising the accuracy results of the benchmark. As a result of this work, the EDDL CPU-optimized version achieves a 2x speedup over the baseline version, executed on Intel Xeon Platinum processo

La secuenciación genómica es un avance científico clave que permite decodificar secuencias de ADN, detectar variaciones genéticas y diagnosticar enfermedades. En la actualidad existen una gran variedad de algoritmos que permiten encontrar mutaciones en secuencias genómicas. La mayoría de estos algoritmos de comparación de secuencias se basan en métodos de programación dinámica. Estos algoritmos presentan costes computacionales prohibitivos para la cantidad masiva de datos producida por los secuenciadores. El objetivo de este proyecto es acelerar los algoritmos de alineamiento de secuencias utilizando un método de pre-filtrado basado en el conteo de k-mers. La seqüenciació genòmica és un avenç científic clau que permet descodificar seqüències d'ADN, detectar variacions genètiques i diagnosticar malalties. En l'actualitat hi ha una gran varietat d'algoritmes que permeten trobar mutacions en seqüències genòmiques. La majoria d'aquests algoritmes de comparació de seqüències es basen en mètodes de programació dinàmica. Aquests algoritmes presenten costos computacionals prohibitius per a la quantitat massiva de dades produïda pels seqüenciadors. L'objectiu d'aquest projecte és accelerar els algoritmes d'alineament de seqüències utilitzant un mètode de pre-filtrat basat en el recompte de k-Mers. Genomic sequencing is a key scientific advance that allows decoding DNA sequences, detecting genetic variations, and diagnosing diseases. Nowadays, there is a great variety of algorithms that allow finding mutations in genomic sequences. Most of these algorithms for sequence comparison are based on dynamic programming methods. These methods present prohibitive computational costs in order to cope with the massive amount of data produced by modern sequencers. The goal of this project is to accelerate sequence alignment algorithms by using a pre-filtering method based k-mers counting.

El alineamiento de secuencias se define como la búsqueda de las diferencias que existen entre dos cadenas de caracteres: patrón y texto. Este trabajo utiliza técnicas de Ingeniería de Rendimiento para caracterizar, optimizar y paralelizar el algoritmo Wavefront Aligner de alineamiento de secuencias. Dicho algoritmo mejora el caso medio comparándolo con otros como el Smith-Waterman. Después de hacer una comparativa de la ejecución del algoritmo en procesadores Intel y ARM, se han desarrollado versiones con paralelización en CPU a distintos niveles de granularidad, obteniendo hasta un 7.5x de speedup. Además, se ha desarrollado una versión en GPU que es capaz de calcular la distancia de edición 13 veces más rápido utilizando secuencias de 1000 bases con una tasa de error de hasta el 10%. De la misma forma, aplicando el algoritmo a secuencias con una tasa de error del 60%, se ha logrado obtener un speedup de 69x. L'alineament de seqüències es defineix com la recerca de les diferències entre dues cadenes de caràcters: patró i text. Aquest treball utilitza tècniques d'Enginyeria de Rendiment per a caracteritzar, optimitzar i paral·lelitzar l'algoritme Wavefront Aligner d'alineament de seqüències. Aquest algoritme millora el cas mitjà comparant-lo amb altres com el Smith-Waterman. Després de fer una comparativa de l'execució de l'algoritme en processadors Intel i ARM, s'han desenvolupat versions amb paral·lelització en CPU a diferents nivells de granularitat, obtenint fins a un 7.5x de speedup. A més, s'ha desenvolupat una versió en GPU que és capaç de calcular la distància d'edició 13 vegades més ràpid utilitzant seqüències de 1000 bases amb una taxa d'error de fins al 10%. De la mateixa manera, aplicant l'algoritme a seqüències amb una taxa d'error dl 60%, s'ha aconseguit obtenir un speedup de 69x. Sequence alignment consists in searching for differences between two strings: pattern and text. The present work employs Performance Engineering techniques to characterize, optimize, and parallelize the Wavefront Alignment algorithm. This algorithm improves on the average case compared with others such as the Smith-Waterman. First, we performed a comparison of the execution of the algorithm Intel and ARM processors. Then, we developed a CPU parallel version, exploiting different levels of granularity, obtaining speedups of 7.5x. Finally, we developed a GPU version that is able to calculate the edit distance 13x faster on sequences of 1000 bases allowing up to 10% of error. In the same way, using the algorithm on sequences up to 60% of error we achieve speedups of 69x.