[en] The cost of sequencing a living being's genome has been greatly reduced due to the advent of Next Generation Secuencing (NGS) techniques. This situation has led to the apparition of many new aligners that can find the position of a given NGS sequence in a reference genome. However, it is difficult to choose the aligner that best adapts to a problem given the shortage of fair comparisons between aligners in terms of alignment effectiveness and computational cost. Besides, another problem commonly faced by bioinformaticians is the correct adjustment of aligner's metaparameters. These difficulties are even greater considering that these aligners are commonly used as black-boxes due to their complexity and the lack of a detailed description and analysis of them. The objective of this Masters Thesis is to provide a theoretical analysis and implementation of three aligners that will serve to compare them, showing which is the best algorithm for each type of NGS sequencing problem. Additionally, this work includes an analysis to determine the influence of aligners' metaparameters in their performance. In order to cover both long and short sequence aligners as well as aligners considering either only mutations (mismatches) or both mutations and gaps, three different aligners, namely Bowtie, BWA and BWT-SW, have been selected for the analysis. These aligners have a common structure, the FM-Index, that allows optimal searching in the reference genome with low memory consumption by using the Burrows-Wheeler transform and its properties. This Masters Thesis offers a description of the hidden details of every algorithm, which has been possible through the thorough study of scientific papers where these algorithms are proposed. Both the FM-Index and the aligners were implemented in C++, and their proper functioning was verified by black and white box unit testing. Once the aligners were implemented, ART software was used to simulate NGS sequences. This software receives as parameters the NGS technology to simulate and other values to control sequences' length, number of mismatches, and gap probability. The behaviour of these three aligners for different values of these parameters has been compared in terms of execution time and hit rate, varying every aligner's metaparameters as well. The outcomes of this Masters Thesis are a detailed study of some of the most used alignment algorithms based on the FM-Index, which intends to complement existing literature; a simple implementation of these aligners, which favors their comprehension and comparison; and a quantitative comparative analysis, which allows us to conclude when each aligner is more suitable than others for an specific sequencing problem.

[es] El coste del proceso de secuenciación de los genomas de los seres vivos, se ha reducido en gran cantidad en los últimos diez años debido a la aplicación de nuevas técnicas de secuenciación denominadas Next Generation Sequencing (NGS). Esta situación ha propiciado la aparición de muchos alineadores que nos permiten, dada una serie de secuencias provenientes de la secuenciación NGS, conseguir hallar la posición en el genoma del que proceden usando un genoma de referencia. Sin embargo es difícil escoger cuál es el alineador que mejor se puede adaptar a cada problema, dada la dificultad de encontrar comparaciones justas entre alineadores en términos de efectividad en la alineación y coste computacional. Además, dentro de un mismo alineador el correcto ajuste de los metaparámetros que definen cada uno de los alineadores es otro problema al que también se enfrentan normalmente los bioinformáticos. Estas dificultades se ven acentuadas por el hecho de que estos alineadores son comúnmente usados como cajas negras dada su complejidad y la dificultad de encontrar descripciones y análisis detallados de los mismos. El objetivo de este TFG es el análisis teórico e implementación de tres alineadores para su posterior comparación, determinando en qué casos es mejor optar por la utilización de unos u otros. Adicionalmente, se proporciona un análisis de la influencia de sus metaparámetros en el rendimiento de cada alineador. Se han escogido Bowtie, BWA y BWT-SW, para cubrir tanto alineadores de secuencias cortas como largas, así como alineadores únicamente tolerantes a mutaciones y alineadores tolerantes a mutaciones y huecos. Estos alineadores usan una estructura común, FM-Index, que les permite realizar búsquedas en el genoma de referencia de forma óptima a través de la transformada de Burrows-Wheeler y propiedades. Este TFG ofrece una descripción detallada del funcionamiento de cada uno de los algoritmos, que ha sido posible tras el análisis de cada uno de los artículos científicos donde se encuentran definidos los mismos. A continuación, tanto los alineadores como el FM-Index se han implementado en C++, y su correcto funcionamiento se ha verificado mediante una serie de pruebas unitarias de caja blanca y caja negra. Una vez implementados, se usó el programa ART para la simulación de un generador de secuencias NGS. Este programa recibe como parámetros la tecnología a simular y otros valores que permiten controlar la longitud de la secuencia de salida y las probabilidades de mutaciones y huecos. Se ha comparado el comportamiento de los tres alineadores para diferentes valores de estos parámetros en términos de tiempos de ejecución y tasas de acierto, haciendo variar a su vez los metaparámetros de cada alineador. Las contribuciones derivadas de este TFG son un estudio detallado del funcionamiento de algunos de los algoritmos de alineación más utilizados, que pretende completar la literatura existente, una implementación sencilla de los mismos que facilita su mejor comprensión y comparación, y un análisis cuantitativo y comparativo de estos alineadores que permite determinar la naturaleza de los problemas de alineación para los cuales cada uno de ellos es más adecuado.