Aceleración de algoritmos de emparejamiento de secuencias genéticas

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ó.