AStarix

AStarix aligns sequences to genome graphs using the A* shortest path algorithm to compute optimal, edit-distance-minimizing alignments with non-negative weights.

Key Features:

• Optimal Alignment: Provides provably optimal sequence-to-graph alignments by minimizing edit distance with non-negative weights.
• A* Algorithm Utilization: Uses the A* shortest path algorithm to find optimal alignments on graph structures.
• Domain-Specific Heuristic: Incorporates a heuristic function tailored to anticipate subsequences of the query sequence to improve search efficiency.
• General Genome Graph Support: Operates on general genome graph structures via an implicit alignment graph representation.
• Problem Transformation: Transforms edit-distance minimization into a shortest-path problem on an implicit alignment graph.
• Experimental Performance: Validated on Illumina reads and reported performance gains of 1–2 orders of magnitude over existing optimal algorithms when aligning Illumina reads to reference genome graphs.

Scientific Applications:

• Genomic Research: Precise sequence alignment to reference genome graphs for genomic studies.
• Illumina Reads Alignment: Aligning Illumina sequencing reads to reference genome graphs as validated experimentally.

Methodology:

Transforms edit-distance minimization into a shortest-path problem on an implicit alignment graph and solves it using the A* algorithm with a domain-specific heuristic that anticipates query subsequences.