Implementación paralela de un método de reconstrucción filogenética para sistemas de memoria distribuida

Abstract

[Resumen]: Uno de los grandes retos computacionales de la bioinformática es el crecimiento exponencial de los datos genómicos, especialmente en tareas como la reconstrucción filogenética, donde se comparan grandes secuencias para inferir relaciones evolutivas. Este Trabajo Fin de Máster aborda esta problemática mediante la paralelización de la herramienta Filtered Spaced-Word Matches (FSWM), un método sin alineamiento diseñado para la estimación eficiente de distancias filogenéticas entre secuencias genómicas. La herramienta FSWM, permite generar una matriz de distancia en formato PHYLIP a partir de la lectura de secuencias genómicas de un archivo en formato FASTA. La versión original incorpora paralelismo mediante OpenMP, lo cual limita su aplicación a equipos de memoria compartida. El objetivo principal de este trabajo es adaptar la herramienta para su ejecución en arquitecturas de memoria distribuida e híbridas mediante el uso de MPI, combinándolo con el paralelismo existente de OpenMP. La propuesta del presente Trabajo Fin de Máster distribuye las comparaciones entre todos los procesos, utilizando MPI. En general, el proceso maestro realiza la lectura de las secuencias de un archivo en formato FASTA y las distribuye a los demás procesos para realizar el cálculo de las distancias de forma paralela. El proceso de cálculo de las distancias utiliza OpenMP. Finalmente, el proceso maestro recopila los resultados parciales y genera la matriz de distancias en formato PHYLIP. Durante el presente trabajo se realizaron múltiples ejecuciones en la supercomputadora Finisterrae III del CESGA utilizando secuencias de bacterias, hongos y plantas. Se obtuvieron reducciones considerables de tiempo de ejecución y aumento del speedup.

[Abstract]: One of the major computational challenges in bioinformatics is the exponential growth of genomic data, especially in tasks such as phylogenetic reconstruction, where large sequences are compared to infer evolutionary relationships. This Master’s Thesis addresses this problem by parallelizing the Filtered Spaced-Word Matches (FSWM) tool, an alignment-free method designed for the efficient estimation of phylogenetic distances between genomic sequences. The FSWM tool, generates a distance matrix in PHYLIP format from genomic sequences read from a FASTA file. The original version incorporates parallelism using OpenMP, which limits its application to shared-memory systems. The main objective of this work is to adapt the tool for execution on distributed and hybrid memory architectures using MPI, combining it with the existing parallelism of OpenMP. The proposal in this Master’s Thesis distributes the comparisons among all processes using MPI. In general, the master process reads the sequences from a FASTA file and distributes them to the other processes to perform the distance calculations in parallel. The distance calculation process uses OpenMP. Finally, the master process compiles the partial results and generates the distance matrix in PHYLIP format. During this work, multiple executions were performed on the Finisterrae III supercomputer at CESGA, using sequences of bacteria, fungi, and plants. Considerable reductions in execution time and increased speedup were achieved.