Haplotype-Aware Sequence Alignment to Pangenome Graphs

Modern pangenome graphs are built using haplotype-resolved genome assemblies. While mapping reads to a pangenome graph, prioritizing alignments that are consistent with the known haplotypes has been shown to improve genotyping accuracy. However, the existing rigorous formulations for sequence-to-graph co-linear chaining and alignment problems do not consider the haplotype paths in a pangenome graph. This often leads to spurious read alignments to those paths that are unlikely recombinations of the known haplotypes. We present novel formulations and algorithms for haplotype-aware sequence alignment to directed acyclic graphs (DAGs). We consider both sequence-to-DAG chaining and sequence-to-DAG alignment problems. Drawing inspiration from the commonly used models for genotype imputation, we assume that a query sequence is an imperfect mosaic of the reference haplotypes. Accordingly, we extend previous chaining and alignment formulations by introducing a recombination penalty for a haplotype switch. First, we solve haplotype-aware sequence-to-DAG alignment in \(O(|Q||E||\mathcal {H}|)\) time where Q is the query sequence, E is the set of edges, and \(\mathcal {H}\) is the set of haplotypes represented in the graph. To complement our solution, we prove that an algorithm significantly faster than \(O(|Q||E||\mathcal {H}|)\) is impossible under the Strong Exponential Time Hypothesis (SETH). Second, we propose a haplotype-aware chaining algorithm that runs in \(O(|\mathcal {H}|N \log {|\mathcal {H}|N})\) time after graph preprocessing, where N is the count of input anchors. We then establish that a chaining algorithm significantly faster than \(O(|\mathcal {H}|N)\) is impossible under SETH. As a proof-of-concept of our algorithmic solutions, we implemented the chaining algorithm in the Minichain aligner ( https://github.com/at-cg/minichain ). We demonstrate the advantage of the algorithm by aligning sequences sampled from human major histocompatibility complex (MHC) to a pangenome graph of 60 MHC haplotypes. The proposed algorithm offers better consistency with ground-truth recombinations when compared to a haplotype-agnostic algorithm.