Biology subjects

Aguado-Puig, Q.

Publications and source records attributed to Aguado-Puig, Q..

3 recordsLinked to original sources

bioRxiv2024

QuickEd: High-performance exact sequence alignment based on bound-and-align

MotivationPairwise sequence alignment is a core component of multiple sequencing-data analysis tools. Recent advancements in sequencing technologies have enabled the generation of longer sequences at a much lower price. Thus, long-read sequencing technologies have become increasingly popular in sequencing-based studies. However, classical sequence analysis algorithms face significant scalability challenges when aligning long sequences. As a result, several heuristic methods have been developed to improve performance at the expense of accuracy, as they often fail to produce the optimal alignment. ResultsThis paper introduces QuickEd, a sequence alignment algorithm based on a bound-and-align strategy. First, QuickEd effectively bounds the maximum alignment-score using efficient heuristic strategies. Then, QuickEd utilizes this bound to reduce the computations required to produce the optimal alignment. Using QuickEds bound-and-align strategy, we reduce O(n2) complexity of traditional dynamic programming algorithms to O(n[s]), where n is the sequence length and[s] is an estimated upper bound of the alignment-score between the sequences. As a result, QuickEd is consistently faster than other state-of-the-art implementations, such as Edlib and BiWFA, achieving performance speedups of 1.6-7.3x and 2.1 - 2.5x, respectively, aligning long and noisy datasets. In addition, QuickEd maintains a stable memory footprint below 50 MB while aligning sequences up to 1 Mbp. AvailabilityQuickEd code and documentation are publicly available at https://github.com/maxdoblas/QuickEd. Contactmax.doblas@bsc.es

bioinformatics↗

bioRxiv2024

BIMSA: Accelerating Long Sequence Alignment Using Processing-In-Memory

MotivationRecent advances in sequencing technologies have stressed the critical role of sequence analysis algorithms and tools in genomics and healthcare research. In particular, sequence alignment is a fundamental building block in many sequence analysis pipelines and is frequently a performance bottleneck both in terms of execution time and memory usage. Classical sequence alignment algorithms are based on dynamic programming and often require quadratic time and memory with respect to the sequence length. As a result, classical sequence alignment algorithms fail to scale with increasing sequence lengths and quickly become memory-bound due to data-movement penalties. ResultsProcessing-In-Memory (PIM) is an emerging architectural paradigm that seeks to accelerate memory-bound algorithms by bringing computation closer to the data to mitigate data-movement penalties. This work presents BIMSA (Bidirectional In-Memory Sequence Alignment), a PIM design and implementation for the state-of-the-art sequence alignment algorithm BiWFA (Bidirectional Wavefront Alignment), incorporating new hardware-aware optimizations for a production-ready PIM architecture (UPMEM). BIMSA supports aligning sequences up to 100K bases, exceeding the limitations of state-of-the-art PIM implementations. First, BIMSA achieves speedups up to 22.24x (11.95x on average) compared to state-of-the-art PIM-enabled implementations of sequence alignment algorithms. Second, achieves speedups up to 5.84x (2.83x on average) compared to the highest-performance multicore CPU implementation of BiWFA. Third, BIMSA exhibits linear scalability with the number of compute units in memory, enabling further performance improvements with upcoming PIM architectures equipped with more compute units and achieving speedups up to 9.56x (4.7x on average). AvailabilityCode and documentation are publicly available at https://github.com/AlejandroAMarin/BIMSA. Contactalejandro.alonso1@bsc.es

bioinformatics↗

bioRxiv2022

WFA-GPU: Gap-affine pairwise alignment using GPUs

MotivationAdvances in genomics and sequencing technologies demand faster and more scalable analysis methods that can process longer sequences with higher accuracy. However, classical pairwise alignment methods, based on dynamic programming (DP), impose impractical computational requirements to align long and noisy sequences like those produced by PacBio, and Nanopore technologies. The recently proposed WFA algorithm paves the way for more efficient alignment tools, improving time and memory complexity over previous methods. However, high-performance computing (HPC) platforms require efficient parallel algorithms and tools to exploit the computing resources available on modern accelerator-based architectures. ResultsThis paper presents the WFA-GPU, a GPU (Graphics Processing Unit)-accelerated tool to compute exact gap-affine alignments based on the WFA algorithm. We present the algorithmic adaptations and performance optimizations that allow exploiting the massively parallel capabilities of modern GPU devices to accelerate the alignment computations. In particular, we propose a CPU-GPU co-design capable of performing inter-sequence and intra-sequence parallel sequence alignment, combining a succinct WFA-data representation with an efficient GPU implementation. As a result, we demonstrate that our implementation outperforms the original multi-threaded WFA implementation between 1.5-7.7x and up to 17x when using heuristic methods on long and noisy sequences. Compared to other state-of-the-art tools and libraries, the WFA-GPU is up to 29x faster than other GPU implementations and up to four orders of magnitude faster than other CPU implementations. AvailabilityWFA-GPU code and documentation are publicly available at https://github.com/quim0/WFA-GPU. Contactquim.aguado@uab.cat

bioinformatics↗