New aligner brings recombination-aware mapping of long reads to pangenome graphs

For years, genomicists have relied on a single linear reference genome as the backbone of read mapping, a convention that quietly discards much of the richness of human genetic diversity. The rise of graph pangenomes has begun to change that. Instead of one canonical sequence, a pangenome encodes a reference that incorporates the evolutionary events observed across a population, including the recombinations that shuffle segments among haplotypes. Variation graphs, a special class of pangenome structures, can represent the full spectrum of variants across multiple genomes far more faithfully than any single linear sequence. Yet a stubborn computational problem has held the field back: aligning sequencing reads against these graphs in a way that properly accounts for recombination events has been too slow to use at scale. A new study published in BMC Bioinformatics by Davide Cesare Monti, Brian Riccardi, Jouni Sirén, Paola Bonizzoni, Gianluca Della Vedova and Raffaella Rizzi, from the University of Milano-Bicocca and the Genomics Institute at the University of California, Santa Cruz, now reports a tool called RecAlign that promises to close that gap.

The motivation behind the work lies in the convergence of two technological currents. Graph pangenomics and long-read sequencing, the authors argue, together hold the promise of integrating read mapping directly with variant calling. A single long read, spanning thousands of DNA letters in one continuous stretch, can provide strong evidence not only for single nucleotide variants but also for larger or more complex structural variations that are notoriously difficult to detect with short reads. Short-read sequencers chop the genome into fragments of a few hundred bases, and when a structural variant spans a region longer than a single fragment, the evidence is scattered and easily missed. Long reads, by contrast, can traverse an entire rearranged segment, carrying the signal for the variant within one molecule. To fully realize this potential, however, the classical algorithms used to align sequences against graphs must be extended to account for recombination events among haplotypes, all while maintaining the practical efficiency that large-scale sequencing projects demand.

Recombination is not a rare curiosity in genome biology; it is a fundamental force that reshapes chromosomes in every generation. When a read originates from a haplotype that inherited one segment from one ancestral path through the pangenome and an adjacent segment from another, an aligner that insists on a single coherent path through the graph will either misalign the read or miss the true origin altogether. Capturing such events formally is what the authors call the R-bounded Recombination-Aware Alignment Problem, abbreviated R-RAAP in the paper. The task is to find the best alignment of a query sequence to a path through a variation graph while allowing a bounded number of recombinations, that is, switches between distinct haplotype paths embedded in the graph. Solving this problem exactly with classical dynamic programming quickly becomes intractable as the number of allowed recombinations grows, because the search space of possible path combinations explodes combinatorially.

The team’s answer to this computational wall is an algorithmic strategy borrowed from artificial intelligence: the A* search framework. A* is a best-first search method that explores a space of possible solutions by prioritizing states that look most promising according to a heuristic function, an estimate of the remaining cost to reach a goal. When the heuristic is admissible, meaning it never overestimates the true remaining cost, A* is guaranteed to find an optimal solution while typically examining only a small fraction of the full search space. RecAlign applies this idea to sequence-to-graph alignment, steering the search through the variation graph toward the alignments that are most likely to be optimal and pruning away the vast regions of the search space that cannot contribute to the best answer. The result, according to the study, is an aligner that is both accurate and fast, and that can efficiently manage two or more recombination events when aligning a read against a variation graph.

The theoretical underpinnings of the work draw on a rich toolkit of combinatorial algorithms and data structures. The abbreviations section of the paper alone signals the depth of the machinery involved: dynamic programming, the longest increasing subsequence problem, the Ferragina-Manzini index better known as the FM-index, and the directed acyclic graph structure that underlies most variation graph representations. The authors also invoke the Strong Exponential Time Hypothesis, a central conjecture in computational complexity theory, which suggests that the recombination-aware alignment problem is unlikely to admit dramatically faster exact algorithms in the worst case. This complexity barrier makes the heuristic-guided pruning of A* not merely a convenience but a necessity: without a way to focus the search, exact recombination-aware alignment would remain confined to toy examples rather than chromosome-scale graphs.

Efficiency alone would not matter if the tool could not be deployed in realistic pipelines. A key contribution of the study is the integration of RecAlign into a chain-and-extend framework, an architectural pattern familiar from classical read aligners, in which short high-confidence matches are first chained together into larger anchors and the alignment is then extended around those anchors. Within this framework, the authors report that RecAlign is currently the only recombination-aware tool that can be used in practice to align long reads against chromosome-wide pangenome graphs. That distinction matters because chromosome-wide graphs, such as those built from the collections of haplotypes assembled by the Human Pangenome Reference Consortium, are precisely the scale at which modern pangenome analyses operate. Tools that can only handle gene-sized or region-sized graphs, however accurate, cannot serve as the mapping engine for whole-genome sequencing experiments.

The biological payoff of recombination-aware alignment is expected to be greatest in the most complex and clinically important regions of the genome. The paper’s list of abbreviations points to the human leukocyte antigen region and the major histocompatibility complex, the hyper-polymorphic immune loci where haplotype diversity is extreme and where short-read mapping has historically struggled most. It also references non-allelic homologous recombination, the mutational mechanism behind many recurrent structural variants, and the Graphical Fragment Assembly and Graph Alignment Format standards that allow graph-based results to flow between tools. By explicitly modeling recombinations among the haplotypes embedded in a variation graph, RecAlign can in principle place reads onto the correct combination of ancestral paths, sharpening downstream variant calling in regions where a linear reference would systematically mislead.

The work did not emerge in isolation. The authors acknowledge helpful discussions with Davide Cozzi and Simone Ciccolella during the development of the project, and the research was carried out within a substantial European funding framework. Monti, Riccardi, Della Vedova, Rizzi and Bonizzoni received support from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement PANGAIA, number 872539, a network dedicated to pangenome algorithms and data structures. The work was further supported by the Horizon Europe programme under project FORGENOM II, identifier 101160008, and partially by the Italian Ministry of University and Research through the Dipartimenti di Eccellenza 2023-2027 grant of the Department of Informatics, Systems and Communication at the University of Milano-Bicocca. Bonizzoni, Della Vedova and Rizzi contributed equally to the study, reflecting a collaboration that spans algorithmic theory and practical bioinformatics engineering.

Consistent with the norms of the field, the implementation is open source and freely available on GitHub under the AlgoLab organization, in the RecGraph repository on the a_star branch, allowing other developers to inspect, reuse and extend the code. The authors declare no competing interests, and all data used in the study were either taken from public repositories or simulated, so no new human subject data were generated. The article is published open access under a Creative Commons Attribution 4.0 International license and was released as a citable, peer-reviewed accepted manuscript with a permanent DOI, subject to further editorial production before the final version of record.

For the broader genomics community, RecAlign represents a step toward a long-standing goal: mapping reads in a way that respects the true evolutionary structure of the population from which they came. As pangenome references grow to encompass ever more diverse haplotypes, and as long-read sequencing becomes routine in clinical and research settings, the algorithms that connect these technologies will determine how much of the genome’s complexity can actually be read out of the data. By showing that recombination-aware alignment can be made fast enough for chromosome-wide graphs, the Milano-Bicocca and UC Santa Cruz team has removed one of the practical obstacles standing between graph pangenomics and its everyday use, and has provided a concrete, tested tool that other groups can now build upon.

Subject of Research: Recombination-aware sequence-to-graph alignment for pangenome read mapping

Article Title: Faster and accurate recombination-aware sequence-to-graph aligner

Article References: Monti, D. C., Riccardi, B., Sirén, J., Bonizzoni, P., Della Vedova, G., & Rizzi, R. (2026). Faster and accurate recombination-aware sequence-to-graph aligner. BMC Bioinformatics. https://doi.org/10.1186/s12859-026-06640-8

Image Credits: AI Generated

DOI: 10.1186/s12859-026-06640-8

Keywords: pangenomics, variation graphs, sequence-to-graph alignment, long-read sequencing, recombination, A* search, RecAlign, BMC Bioinformatics, variant calling, FM-index, Human Pangenome Reference Consortium, computational biology