Graph Wavefront Algorithm

Graph wavefront algorithm

Recently, we have proposed graph wavefront algorithm, which is an efficient sequence-to-graph alignment algorithm in practice. The implementation termed Gwfa is available here. Tested on 4 real sequence graphs, Gwfa with a pruning heuristic achieved up to 5 orders of magnitude speedup compared with other sequence-to-graph alignment methods.

Though the Gwfa preprint contains a formal description of the algorithm, it might not be easy for one without any experience in wavefront alignment algorithm (WFA) to understand. Therefore, I made a tutorial video to explain the idea on how Gwfa works with an example. The slides are available here. Hope these materials can be helpful.