Aceleración del algoritmo Wavefront Aligner para emparejamiento de secuencias genéticas
Hernández Chinappi, Ernesto
Marco-Sola, Santiago, dir. (Universitat Autònoma de Barcelona. Departament d'Arquitectura de Computadors i Sistemes Operatius)
Moure, Juan C, dir. (Universitat Autònoma de Barcelona. Departament d'Arquitectura de Computadors i Sistemes Operatius)
Universitat Autònoma de Barcelona. Escola d'Enginyeria

Additional title:	Acceleració de l'algorisme Wavefront Aligner per aparellament de seqüències genètiques
Additional title:	Acceleration of the Wavefront Aligner algorithm for pairing genetic sequences
Date:	2020
Abstract:	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.
Abstract:	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.
Abstract:	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.
Rights:	Aquest document està subjecte a una llicència d'ús Creative Commons. Es permet la reproducció total o parcial i la comunicació pública de l'obra, sempre que no sigui amb finalitats comercials, i sempre que es reconegui l'autoria de l'obra original. No es permet la creació d'obres derivades.
Language:	Castellà
Studies:	Grau en Enginyeria Informàtica [2502441]
Study plan:	Enginyeria Informàtica [958]
Document:	Treball final de grau ; Text
Subject area:	Menció Enginyeria de Computadors
Subject:	Alineamiento de secuencias ; Distancia de edición ; Ingeniería de rendimiento ; Computación de altas prestaciones ; Bioinformática ; Alineament de seqüències ; Distància d'edició ; Wavefront Aligner ; GPU ; Enginyeria de rendiment ; Computació d'altes prestacions ; Bioinformàtica ; Sequence alignment ; Edit distance ; Wavefront Alignment ; Performance Engineering ; High Performance Computing ; Bioinformatics

9 p, 405.6 KB

The record appears in these collections:
Research literature > Bachelor's degree final project > School of Engineering. TFG