Faster and accurate recombination-aware sequence-to-graph aligner

Motivation Graph pangenomics and long-read sequencing hold the promise of integrating read mapping with variant calling. A pangenome encodes a reference that incorporates evolutionary events in a population, such as recombinations among haplotypes. In particular variation graphs, a special class of graph pangenomes, are able to more accurately represent the variants across multiple genomes. On the other hand, a single long read can provide strong evidence for certain variants, not only single nucleotide variants (SNVs) but also larger or more complex variations that are difficult to detect with short reads [1]. To fully realize this potential, we need to extend classical sequence-to-graph alignment algorithms to account for recombination events among haplotypes in variation graphs while maintaining practical efficiency. Results By leveraging an A* approach, we develop RecAlign: an accurate and fast sequence-to-graph aligner against a variation graph that is able to manage efficiently two or more recombinations. When integrated into a chain-and-extend framework, RecAlign is currently the only recombination-aware tool that can be used to align long reads against chromosome-wide pangenome graphs in practice. Availability Our implementation is open source and available at https://github.com/AlgoLab/RecGraph/tree/a_star.