RecGraph

RecGraph computes optimal sequence-to-graph alignment with recombinations.

Key Features:

• Recombination-aware alignment: Extends sequence-to-graph alignment to variation graphs by explicitly representing and evaluating recombinations in the alignment.
• Dynamic programming implementation: Implements a dynamic programming approach for the special case where there is at most one recombination.
• Recombination path modelling: Models a recombination as identifying a new path of the variation graph, where the new arc is composed of two halves, each extracted from an original path, possibly joined by a new arc.

Scientific Applications:

• Bacterial pangenomics: Accurately aligns simulated recombinant bacterial sequences that have at most a recombination, providing evidence for the presence of recombination events.
• Homologous recombination detection: Captures mosaic structure in bacterial genomes caused by homologous recombinations that standard read mappers against linear reference genomes do not sufficiently capture.

Methodology:

RecGraph uses a dynamic programming approach for sequence-to-graph alignment that incorporates at most one recombination.