RecAlign: A* recombination-aware sequence to graph mapping

Abstract

Pangenomics and long reads bring the promise of integrating read mapping with variant calling, since a pangenome encodes a reference genome that incorporates evolutionary or population aspects, while even a single long read can provide a good evidence of different kinds of variants (not only the single nucleotide variants that can be easily observed by short reads). This promise needs to be fulfilled by the development of new read mapping approaches that are tailored for that purpose. This paper focuses on integrating recombination events, that are key in bacteria, into read mapping. A first approach in that direction [ACBC+24] provides an exact dynamic programming algorithm that is too slow to manage multiple recombinations or long reads. We present a novel A* algorithm for recombination-aware sequence-to-graph mapping that significantly reduces running time by incorporating haplotype information and an efficient heuristic function. Our tool, RecAlign, demonstrates up to a two-order magnitude improvement in time and space complexity over [ACBC+24] and efficiently handles multiple recombinations.