[ca] L'alineament múltiple de seqüències (MSA) ha esdevingut fonamental per tal de realitzar anàlisis de seqüències a l'era de la biologia moderna. Amb l'arribada de les tecnologies de seqüenciació de nova generació d'alt rendiment (NGS), el volum de dades generades pels seqüenciadors s'ha incrementat significativament. Per tant, s'han de definir nous alineadors que puguin treballar a gran escala. No obstant això, la naturalesa heurística dels mètodes MSA juntament amb la complexitat computacional (NP-hard) està alentint l'anàlisi d'alineaments a gran escala que involucren milers de seqüències o fins i tot a genomes complets. A més, la qualitat d'aquests alineaments es veu dràsticament reduïda quan s'incrementa el nombre de seqüències. Els alineadors basats en consistència asseguren mitigar aquest problema mitjançant la inclusió d'informació precalculada (anomenada com a llibreria de consistència) per cada parell de seqüències a tractar a la fase d'alineament. Aquests mètodes son capaços de produir alineaments d'alta qualitat. No obstant això, mantenir aquest gran volum d'informació, que involucra a tots els parells de seqüències, a memòria limita la quantitat de seqüències que es poden tractar simultàniament. L'objectiu d'aquest PhD és l'estudi i proposta de nous mètodes i eines per tal de permetre, als MSA basats en consistència, la capacitat d'escalar processant conjunts de dades molt més grans, millorant el rendiment i la qualitat de l'alineament. El principal obstacle per tal d'aconseguir dita escalabilitat en aquests mètodes són els requisits de recursos de la llibreria (memòria i temps de còmput) els quals creixen quadràticament amb el nombre de seqüències. Al present treball de tesis es proposen dos mètodes per millorar l'escalabilitat: 1) reduir la informació de la llibreria per tal de mantenir-la a memòria; i 2) emmagatzemar les dades de la llibreria a un sistema d'emmagatzemament secundari distribuït, utilitzant els nous paradigmes de Big Data (MapReduce, bases de dades no-sql) i arquitectures (Hadoop) per calcular, mantenir i accedir a la llibreria eficientment. A més de l'enfocament computacional, s'ha desenvolupat una nova funció objectiu secundària que permet incrementar la qualitat de l'alineament final. Els resultats demostren l'efectivitat de les propostes, les quals milloren l'escalabilitat, rendiment i qualitat de T-Coffee, l'eina emprada per validar les diferents propostes.

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