Publication

On the optimization of GWFA algorithm: enabling real-case applications supporting alignment backtracking

Abstract blue and green light streaks, cover of the publication on optimizing the GWFA algorithm for alignment backtracking

Pangenome graphs describe the genetic variability of a population more accurately than a single linear reference. Aligning long reads end to end against these graphs is essential to find structural variations, and the Graph Wavefront Alignment (GWFA) algorithm is the fastest approach available. However, its original implementation could not report how each read aligns (the alignment traceback), a feature real studies require.

This work delivers a new open-source GWFA implementation that produces the full traceback in the standard GAF format. It runs 20x faster than the state-of-the-art tool GraphAligner, with competitive memory usage.

Authors: Mirko Coggi, Antonio Sgarlata, Guido Walter Di Donato, Marco Domenico Santambrogio

Published in: IEEE Engineering in Medicine and Biology Society Conference (EMBC), 2024