High performance computing on biological sequence alignment

dc.contributor
Universitat de Lleida. Departament d'Informàtica i Enginyeria Industrial
dc.contributor.author
Orobitg Cortada, Miquel
dc.date.accessioned
2013-05-03T13:31:52Z
dc.date.available
2013-05-03T13:31:52Z
dc.date.issued
2013-04-17
dc.identifier.uri
http://hdl.handle.net/10803/110930
dc.description.abstract
L'Alineament Múltiple de Seqüències (MSA) és una eina molt potent per a aplicacions biològiques importants. Els MSA són computacionalment complexos de calcular, i la majoria de les formulacions porten a problemes d'optimització NP-Hard. Per a dur a terme alineaments de milers de seqüències, nous desafiaments necessiten ser resolts per adaptar els algoritmes a l'era de la computació d'altes prestacions. En aquesta tesi es proposen tres aportacions diferents per resoldre algunes limitacions dels mètodes MSA. La primera proposta consisteix en un algoritme de construcció d'arbres guia per millorar el grau de paral•lelisme, amb la finalitat de resoldre el coll d'ampolla de l'etapa de l'alineament progressiu. La segona proposta consisteix en optimitzar la biblioteca de consistència per millorar el temps d'execució, l'escalabilitat, i poder tractar un major nombre de seqüències. Finalment, proposem Multiples Trees Alignment (MTA), un mètode MSA per alinear en paral•lel múltiples arbres guia, avaluar els alineaments obtinguts i seleccionar el millor com a resultat. Els resultats experimentals han demostrat que MTA millora considerablement la qualitat dels alineaments. El Alineamiento Múltiple de Secuencias (MSA) es una herramienta poderosa para aplicaciones biológicas importantes. Los MSA son computacionalmente complejos de calcular, y la mayoría de las formulaciones llevan a problemas de optimización NP-Hard. Para llevar a cabo alineamientos de miles de secuencias, nuevos desafíos necesitan ser resueltos para adaptar los algoritmos a la era de la computación de altas prestaciones. En esta tesis se proponen tres aportaciones diferentes para resolver algunas limitaciones de los métodos MSA. La primera propuesta consiste en un algoritmo de construcción de árboles guía para mejorar el grado de paralelismo, con el fin de resolver el cuello de botella de la etapa del alineamiento progresivo. La segunda propuesta consiste en optimizar la biblioteca de consistencia para mejorar el tiempo de ejecución, la escalabilidad, y poder tratar un mayor número de secuencias. Finalmente, proponemos Múltiples Trees Alignment (MTA), un método MSA para alinear en paralelo múltiples árboles guía, evaluar los alineamientos obtenidos y seleccionar el mejor como resultado. Los resultados experimentales han demostrado que MTA mejora considerablemente la calidad de los alineamientos. Multiple Sequence Alignment (MSA) is a powerful tool for important biological applications. MSAs are computationally difficult to calculate, and most formulations of the problem lead to NP-Hard optimization problems. To perform large-scale alignments, with thousands of sequences, new challenges need to be resolved to adapt the MSA algorithms to the High-Performance Computing era. In this thesis we propose three different approaches to solve some limitations of main MSA methods. The first proposal consists of a new guide tree construction algorithm to improve the degree of parallelism in order to resolve the bottleneck of the progressive alignment stage. The second proposal consists of optimizing the consistency library, improving the execution time and the scalability of MSA to enable the method to treat more sequences. Finally, we propose Multiple Trees Alignments (MTA), a MSA method to align in parallel multiple guide-trees, evaluate the alignments obtained and select the best one as a result. The experimental results demonstrated that MTA improves considerably the quality of the alignments.
eng
dc.format.extent
208 p.
cat
dc.format.mimetype
application/pdf
dc.language.iso
eng
cat
dc.publisher
Universitat de Lleida
dc.rights.license
L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc-sa/3.0/es/
dc.rights.uri
http://creativecommons.org/licenses/by-nc-sa/3.0/es/
*
dc.source
TDX (Tesis Doctorals en Xarxa)
dc.subject
Alineament múltiple de seqüències
cat
dc.subject
Computació d'altes prestacions
cat
dc.subject
Escalabilitat
cat
dc.subject
Alineamiento múltiple de secuencias
cat
dc.subject
Computación de altas prestaciones
cat
dc.subject
Escalabilidad
cat
dc.subject.other
Arquitectura i Tecnologia de Computadors
cat
dc.title
High performance computing on biological sequence alignment
cat
dc.type
info:eu-repo/semantics/doctoralThesis
dc.type
info:eu-repo/semantics/publishedVersion
dc.subject.udc
004
cat
dc.contributor.codirector
Cores Prado, Fernando
dc.contributor.codirector
Guirado Fernández, Fernando
dc.embargo.terms
cap
cat
dc.rights.accessLevel
info:eu-repo/semantics/openAccess
dc.identifier.dl
L.290-2013
cat


Documentos

Tmoc1de1.pdf

4.927Mb PDF

Este ítem aparece en la(s) siguiente(s) colección(ones)