Aceleración de algoritmos de emparejamiento de secuencias genéticas
Gutiérrez Martín, Francisco
Moure, Juan C, dir. (Universitat Autònoma de Barcelona. Departament d'Arquitectura de Computadors i Sistemes Operatius)
Marco-Sola, Santiago, dir. (Universitat Autònoma de Barcelona. Departament d'Arquitectura de Computadors i Sistemes Operatius)
Universitat Autònoma de Barcelona. Escola d'Enginyeria

Títol variant:	Acceleration of genetic sequence matching algorithms
Títol variant:	Acceleració d'algoritmes d'aparellament de seqüències genètiques
Data:	2018-07-11
Resum:	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.
Resum:	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.
Resum:	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ó.
Drets:	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.
Llengua:	Castellà
Titulació:	Grau en Enginyeria Informàtica [2502441]
Pla d'estudis:	Enginyeria Informàtica [958]
Document:	Treball final de grau ; Text
Àrea temàtica:	Menció Enginyeria de Computadors
Matèria:	Distància d'Edició ; Programació Dinàmica ; Alineament Diagonal ; Matriu de distància ; Enginyeria de Rendiment ; Computació d'Altes Prestacions ; Bioinformàtica ; Distancia de Edición ; Programación Dinámica ; Alineamiento Diagonal ; Matriz de Distancia ; Ingeniería de Rendimiento ; Computación de Altas Prestaciones ; Bioinformática ; Edit Distance ; Dynamic Programming ; Diagonal Matching ; Distance Matrix ; Performance Engineering ; High Performance Computing ; Bioinformatics

9 p, 1.4 MB

El registre apareix a les col·leccions:
Documents de recerca > Treballs de Fi de Grau > Escola d'Enginyeria. TFG