Accelerated Algorithms for Sequence Alignment in Bioinformatic Applications

Abstract

Els ràpids avenços tecnològics en la seqüenciació del genoma han permès l'estudi dels genomes a escala poblacional, impulsant nous descobriments biològics i biomèdics. Tanmateix, l'augment ràpid en la generació de dades genòmiques planteja reptes significatius per a l'escalabilitat de les eines d'anàlisi existents. Actualment, l'alineament de seqüències és una operació central en la majoria de fluxos de treball de bioinformàtica, exercint un paper clau en tasques com el muntatge de genomes, la detecció de variants i la genòmica comparativa. No obstant això, l'escala creixent de les dades de seqüenciació ha convertit els algorismes tradicionals d'alineament de seqüències en un important coll d'ampolla computacional. Per aquest motiu, accelerar l'alineament de seqüències és essencial per permetre una anàlisi genòmica eficient i escalable, amb implicacions directes per a la recerca i per a aplicacions clíniques, inclosa la medicina de precisió. Aquesta tesi proposa el desenvolupament d'algorismes millorats per a l'alineament seqüència-a-seqüència, aprofitant tècniques avançades de programació dinàmica i estratègies d'optimització. En particular, explora algorismes output-sensitive que exploten les similituds entre seqüències per guiar l'alineament i accelerar el còmput, podant l'espai de cerca i reduint el nombre d'estats de programació dinàmica explorats, tot garantint solucions òptimes. L'objectiu és dissenyar algorismes eficients que preservin la precisió alhora que redueixin significativament els costos computacionals, permetent-ne la seva integració en fluxos de treball de bioinformàtica del món real. Accelerar l'alineament de seqüències és clau per a l'eficiència dels fluxos de treball d'anàlisi genòmica i permet estudis a escala poblacional. En darrer terme, aquest treball pretén contribuir a l'acceleració dels fluxos de treball d'anàlisi genòmica per a estudis de recerca genòmica a gran escala. Amb aquest objectiu, l'avaluació experimental mostra una acceleració de més de 10x en comparació amb alguns algoritmes d'alineament de seqüències utilitzats avui en dia.

Rapid technological advances in genome sequencing have enabled the study of genomes at the population scale, driving new biological and biomedical discoveries. However, the rapid increase in genomic data generation poses significant challenges to the scalability of existing analysis tools. Nowadays, sequence alignment is a core operation in most bioinformatics pipelines, playing a critical role in tasks such as genome assembly, variant calling, and comparative genomics. However, the growing scale of sequencing data has made traditional sequence alignment algorithms a major computational bottleneck. Hence, accelerating sequence alignment is essential for enabling efficient and scalable genomic analysis, with direct implications for research and clinical applications, including precision medicine. This thesis proposes the development of improved algorithms for sequence-to-sequence alignment, leveraging advanced dynamic programming techniques and optimization strategies. In particular, it explores output-sensitive algorithms that exploit the similarities between sequences to align and accelerate computation, pruning the search space and reducing the number of dynamic programming states explored while still guaranteeing optimal solutions. The goal is to design efficient algorithms that preserve accuracy while significantly reducing computational costs, enabling their integration into real-world bioinformatics pipelines. Accelerating sequence alignment is key to the efficiency of genome analysis pipelines and enables studies at the population scale. Ultimately, this work aims to contribute to accelerating genome analysis pipelines for large-scale genomic research studies. To this end, the experimental evaluation reports more than 10x of speed-up compared to some sequence alignment algorithms used nowadays.