An algorithm to align a chain of sequences to paths in a pangenome graph
Authors
Gorkem Kadir Solun
Ugur Dogrusoz
Abstract
Affordable, high-quality whole-genome assemblies have made it possible to construct rich pangenomes that capture haplotype diversity across many species. As these datasets grow, they motivate the development of specialized techniques capable of handling the dense sequence variation found in large groups of related genomes. A common strategy is to encode pangenomic information in graph form, which provides a flexible substrate for improving algorithms in areas such as alignment, visualization, and functional analysis. Methods built on these graph models have already shown clear advantages in core bioinformatics workflows, including read mapping, variant discovery, and genotyping. By integrating multiple sequence and coordinate representations into a single structure, pangenome graphs offer a unified and expressive framework for comparative genomics. Although it remains unclear whether graph-based references will ultimately supplant traditional linear genomes, their versatility ensures that they will play a central role in emerging pangenomic approaches. This paper introduces an algorithm to mine a chain of sequences in pangenome graphs that might be useful in the functional analysis of pangenome graphs. Specifically, the algorithm calculates all maximal paths in a pangenome graph aligning with a given chain of sequences in the segments of the path vertices, possibly with some maximal gap as specified by the user.
