[en] Multiple Sequence Alignment (MSA) has become fundamental for performing sequence analysis in modern biology. With the advent of new high-throughput Next Generation Sequencing (NGS) technologies, the volume of data generated by sequencers has increased significantly. Thus, large-scale aligners are required. However, the heuristic nature of MSA methods together with their NP-hard computational complexity is slowing down the analysis of large-scale alignments with thousands of sequences or even whole genomes. Moreover, the accuracy of these methods is being drastically reduced when more sequences are aligned. Consistency methods proven to mitigate such errors add precomputed information (consistency library) for each pairwise to the alignment stage, and are capable of producing high-rated alignments. However, maintaining this whole collection of pairwise information in the memory limits the maximum number of sequences that can be dealt with at once. The objective of this PhD is the study and proposal of new methods and tools to enable scalability for consistency-based MSA aligners, processing bigger datasets, improving their overall performance and the alignment accuracy. The main obstacle to attain scalability on such methods is the library resource requirements (both memory and computing time) that grows quadratically with the number of sequences. Two methods are proposed to improve the scalability: 1) reducing the library information in order to fit it into the memory; and 2) storing the library data in secondary distributed storage, using the new Big Data paradigms (MapReduce, no-sql databases) and architectures (Hadoop) to calculate, store and access the library efficiently. In addition to the computational approaches, we propose an innovative secondary objective function to increase the accuracy of the final alignment. The results demonstrate the effectiveness of the proposals, which improve the scalability, performance and accuracy of T-Coffee, the tool used to validate the different proposals.

[es] El alineamiento múltiple de secuencias (MSA) se ha demostrado como fundamental para poder realizar análisis de secuencias en la era de la biología moderna. Con la llegada de las tecnologías de secuenciación de nueva de generación y de altas prestaciones (NGS), el volumen de datos generados por los secuenciadores se ha incrementado significativamente. Por este motivo, es necesario desarrollar alineadores capaces de trabajar a gran escala. No obstante, la naturaleza heurística de los metodos de MSA, juntamente con su complejidad computacional (NP-hard) está retrasando el análisis de alineamientos a gran escala que involucran miles de secuencias o incluso a genomas completos. Además, la calidad de estos alineamientos se ve drásticamente reducida cuando se incrementa el número de secuencias a alinear. Los alineadores basados en consistencia permiten mitigar este problema añadiendo información precalculada (denominada librería de consistencia) para cada par de secuencias a tratar en la fase de alineamiento. Estos métodos son capaces de producir alineamientos de alta calidad. No obstante, almacenar este gran volumen de información, que involucra a todos los pares de secuencias, en memoria limita la cantidad de secuencias que se pueden tratar simultaneamente. El objetivo de este PhD es el estudio y propuesta de nuevos métodos y herramientas que permitan a los MSA basados en consistencia, escalar (procesando un mayor número de secuencias), mejorando el rendimiento y la calidad del alineamiento. El principal obstáculo para lograr dicha escalabilidad en estos métodos son los requisitos de recursos de la librería (memoria y tiempo de cómputo) los cuales crecen cuadráticamente con el número de secuencias. En el presente trabajo de tesis, se proponen dos métodos para mejorar la escalabilidad: 1) reducir la información de la librería para poder así mantenerla en memoria; y 2) almacenar los datos de la librería en un sistema de almacenamiento secundario distribuido, usando los nuevos paradigmas de Big Data (MapReduce, bases de datos no-sql) y arquitecturas (Hadoop) para calcular, almacenar y acceder a la librería eficientemente. Además del enfoque computacional, se ha desarrollado una nueva función objetivo secundaria para incrementar la calidad del alineamiento final. Los resultados demuestran la efectividad de las propuestas, las cuales mejoran la escalabilidad, rendimiento y calidad de T-Coffee, la herramienta utilizada para validar las diferentes propuestas.