Universitat de Lleida
Guirado Fernández, Fernando
Cores Prado, Fernando
2018-07-20
91 p.
Universitat de Lleida. Departament d'Informàtica i Enginyeria Industrial
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.
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.
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.
Alineament Múltiple de Seqüències; Big Data; Basat en consistència; Alineamiento Múltiple de Secuencias; Basado en consistencia; Multiple Sequence Alignment; Consistency-based
004 - Computer science and technology. Computing. Data processing
Arquitectura i Tecnologia de Computadors
ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs.
