Biology subjects

Dabbaghie, F.

Publications and source records attributed to Dabbaghie, F..

7 recordsLinked to original sources

bioRxiv2025

Accelign: a GPU-based Library for Accelerating Pairwise Sequence Alignment

BackgroundThe continually increasing volume of sequence data results in a growing demand for fast implementations of core algorithms. Computation of pairwise alignments based on dynamic programming is an important part in many bioinformatics pipelines and a major contributor to overall runtime due to the associated quadratic time complexity. This motivates the need for a library of efficient implementations on modern GPUs for a variety of alignment algorithms for different types of sequence data including DNA, RNA, and proteins. ResultsAccelign is a library of accelerated pairwise sequence alignment algorithms for CUDA-enabled GPUs. Its parallelization strategy is based on a common wavefront design that can be adapted to support a variety of dynamic programming algorithms: local, global, and semi-global alignment of genomic and protein sequences with a variety of commonly used scoring schemes supporting one-to-one, one-to-many or all-to-all pairwise sequence alignments. This leads to a peak performance between 16.1 TCUPS and 9.1 TCUPS for computing optimal global alignment scores with linear gaps and affine gap penalties on a single RTX PRO 6000 Blackwell GPU, respectively. In addition, our library demonstrates significant speedups in several real-world case studies over prior CPU-based (SeqAn, Parasail, BSalign) and GPU-based libraries (ADEPT, GASAL2), and can even outperform highly customized algorithms (WFA-GPU, CUDASW++4.0). Furthermore, the performance of our approach scales linearly with the number of employed GPUs, which makes it feasible to exploit multi-GPU nodes for increased processing speeds. ConclusionAccelign provides significant speedups for commonly used pairwise alignment algorithms compared to prior implementations. It is freely available at https://github.com/fkallen/Accelign.

bioinformatics↗

bioRxiv2024

EpiPAMPAS: Rapid detection of intra-protein epistasis via parsimonious ancestral state reconstruction and counting mutations

MotivationAn epistatic interaction is a non-linear combination of effects of individual mutations on fitness. This type of interaction is a known driver for evolution, as they alter the organisms fitness and adaptability. In this work we introduce EpiPAMPAS, a statistical method that is based on multiple sequence alignments (MSA) and detecting mutations in the same direction on a dendrogram instead of a phylogenetic tree using the Sankoff algorithm. ResultsWe tested EpiPAMPAS on both simulated and real sequencing data. On the simulated data, our method was able to detect the simulated epistatic pairs with very low p-value. In a real-world application, we tested the influenza proteins N1, N2, H1, H3 and HIV-1 envelope protein subtypes A, B and C. We observe that EpiPAMPAS detects fewer interacting pairs than comparable statistical approaches, although the overlap between detected positions is good. Moreover, some of the amino acids from the detected pairs are known to be deleterious for viral fitness. AvailabilityEpiPAMPAS is available under MIT license at https://github.com/kalininalab/EpiPAMPAS

bioinformatics↗

bioRxiv2024

gaftools: a toolkit for analyzing and manipulating pangenome alignments

Linear reference genomes are ubiquitously used in genomics research, despite known biases associated with their use. In recent years, there has a been a shift towards using graph-based reference genomes to address some of these biases, which has required new algorithms and file formats to be developed. This has created the need to develop new tools capable of utilizing these formats and performing operations similar to those carried out by traditional methods.In this paper we present "gaftools", a multi-purpose tool that introduces several utilities for processing graph alignments in GAF format. Gaftools enables users to index and sort alignments, with graph ordering serving as a necessary step for the sorting process. Additionally it allows users to view subsets of alignments and perform realignment using the wavefront alignment algorithm, among other useful features. Many of these functionalities are inspired by SAMtools, which provide similar operations for linear genomes, while gaftools adapts and extends them for pangenomes. Availabilitygaftools is available under MIT license at https://github.com/marschall-lab/gaftools.

bioinformatics↗

bioRxiv2024

extgfa: a low-memory on-disk representation of genome graphs

The representation of genomes and genomic sequences through graph structures has undergone a period of rapid development in recent years, particularly to accommodate the growing size of genome sequences that are being produced. Genome graphs have been employed extensively for a variety of purposes, including assembly, variance detection, visualization, alignment, and pangenomics. Many tools have been developed to work with and manipulate such graphs. However, the majority of these tools tend to load the complete graph into memory, which results in a significant burden even for relatively straightforward operations such as extracting subgraphs, or executing basic algorithms like breadth-first or depth-first search. In procedurally generated open-world games like Minecraft, it is not feasible to load the complete world into memory. Instead, a mechanism that keeps most of the world on disk and only loads parts when needed is necessary. Accordingly, the world is partitioned into chunks which are loaded or unloaded based on their distance from the player. Furthermore, to conserve memory, the system unloads chunks that are no longer in use based on the players movement direction, sending them back to the disk. In this paper, we investigate the potential of employing a similar mechanism on genome graphs. To this end, we have developed a proof-of-concept implementation, which we called "extgfa" (for external GFA). Our implementation applies a similar chunking mechanism to genome graphs, whereby only the necessary parts of the graphs are loaded and the rest stays on disk. We demonstrate that this proof-of-concept implementation improves the memory profile when running an algorithm such as BFS on a large graph, and is able to reduce the memory profile by more than one order of magnitude for certain BFS parameters. AvailabilityOur implementation is written in Python and available on Github under the MIT license https://github.com/fawaz-dabbaghieh/extgfa

bioinformatics↗

bioRxiv2023

PanPA: generation and alignment of panproteome graphs

MotivationCompared to eukaryotes, prokaryote genomes are more diverse through different mechanisms, including a higher mutation rate and horizontal gene transfer. Therefore, using a linear representative reference can cause a reference bias. Graph-based pangenome methods have been developed to tackle this problem. However, comparisons in DNA space is still challenging due to this high diversity. In contrast, amino acids have higher similarity due to evolutionary constraints, resulting in conserved amino acids that, however, may be encoded by several synonymous codons. Coding regions cover the majority of the genome in prokaryotes. Thus, building panproteomes leverages the high sequence similarity while not losing much of the genome in non-coding regions. ResultsWe present PanPA, a method that takes a set of multiple sequence alignments (MSAs) of proteins or protein clusters, indexes them, and builds a graph for each MSA. In the querying step, it can align DNA or amino acid sequences back to these graphs. We first showcase that PanPA generates correct alignments on a panproteome from 1,350 E. coli. To demonstrate that panproteomes allow longer phylogenetic distance comparison, we compare DNA and protein alignments from 1,073 S. enterica assemblies against E. coli reference genome, pangenome, and panproteome using BWA, GraphAligner, and PanPA respectively, where PanPA was able to produce around 22% more alignments. We also aligned DNA short-reads WGS sample from S. enterica against the E. coli reference with BWA and the panproteome with PanPA, where PanPA was able to find alignment for 69% of the reads compared to 5% with BWA AvailabilityPanPA is available at https://github.com/fawaz-dabbaghieh/PanPA Contactfawaz@hhu.de, olga.kalinina@helmholtz-hzi.de Supplementary informationSupplementary data are available at Bioinformatics online.

bioinformatics↗

bioRxiv2021

MetaProFi: A protein-based Bloom filter for storing and querying sequence data for accurate identification of functionally relevant genetic variants

Technological advances of next-generation sequencing present new computational challenges to develop methods to store and query these data in time- and memory-efficient ways. We present MetaProFi (https://github.com/kalininalab/metaprofi), a Bloom filter-based tool that, in addition to supporting nucleotide sequences, can for the first time directly store and query amino acid sequences and translated nucleotide sequences, thus bringing sequence comparison to a more biologically relevant protein level. Owing to the properties of Bloom filters, it has a zero false-negative rate, allows for exact and inexact searches, and leverages disk storage and Zstandard compression to achieve high time and space efficiency. We demonstrate the utility of MetaProFi by indexing UniProtKB datasets at organism- and at sequence-level in addition to the indexing of Tara Oceans dataset and the 2585 human RNA-seq experiments, showing that MetaProFi consumes far less disk space than state-of-the-art-tools while also improving performance.

bioinformatics↗

bioRxiv2021

BubbleGun: Enumerating Bubbles and Superbubbles in Genome Graphs

MotivationWith the fast development of third generation sequencing machines, de novo genome assembly is becoming a routine even for larger genomes. Graph-based representations of genomes arise both as part of the assembly process, but also in the context of pangenomes representing a population. In both cases, polymorphic loci lead to bubble structures in such graphs. Detecting bubbles is hence an important task when working with genomic variants in the context of genome graphs. ResultsHere, we present a fast general-purpose tool, called BubbleGun, for detecting bubbles and superbubbles in genome graphs. Furthermore, BubbleGun detects and outputs runs of linearly connected bubbles and superbubbles, which we call bubble chains. We showcase its utility on de Bruijn graphs and compare our results to vgs snarl detection. We show that BubbleGun is considerably faster than vg especially in bigger graphs, where it reports all bubbles in less than 30 minutes on a human sample de Bruijn graph of around 2 million nodes. AvailabilityBubbleGun is available and documented at https://github.com/fawaz-dabbaghieh/bubble_gun under MIT license. Contactfawaz@hhu.de or tobias.marschall@hhu.de Supplementary informationSupplementary data are available at Bioinformatics online.

bioinformatics↗